BZOJ 1093 ZJOI 2007 最大半连通子图 强联通分量+拓扑图DP
题目大意:定义半连通图:图中任意两点之间可以单向到达。求一个图的最大半连通子图,和这个图最大半连通子图的个数。
思路:半连通图并不是一定要没有环。。这题意让我理解的。。
其实想法什么的不难,想明白了也不难写。因为要保证半连通,所以要先处理出一个图的联通状况。先用Tarjan缩点得到DAG,在这个DAG上找到最长链的长度就是第一问的答案。第二问可以先找到所有f值等于答案的点,在这些点上反向记忆化搜索DP。
注意一个小地方,ans的初值是最大的scc的大小,如果是0的化会wa一个点。
CODE:
#include <set> #include <queue> #include <vector> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define MAXP 100010 #define MAX 2000010 using namespace std; #define max(a,b) ((a) > (b) ? (a):(b)) int points,edges,p; int head[MAXP],total; int next[MAX],aim[MAX]; set<pair<int,int> > G; void Add(int x,int y) { next[++total] = head[x]; aim[total] = y; head[x] = total; } int dfn[MAXP],low[MAXP],_clock; int stack[MAXP],top; bool in_stack[MAXP]; int changed[MAXP],scc,cnt[MAXP]; void Tarjan(int x) { dfn[x] = low[x] = ++_clock; stack[++top] = x; in_stack[x] = true; for(int i = head[x]; i; i = next[i]) { if(!dfn[aim[i]]) Tarjan(aim[i]),low[x] = min(low[x],low[aim[i]]); else if(in_stack[aim[i]]) low[x] = min(low[x],dfn[aim[i]]); } if(dfn[x] == low[x]) { int temp; ++scc; do { temp = stack[top--]; in_stack[temp] = false; changed[temp] = scc; ++cnt[scc]; }while(temp != x); } } namespace DAG { int head[MAXP],total; int next[MAX],aim[MAX]; int _in[MAXP]; vector<int> from[MAXP]; int f[MAXP],memory[MAXP]; int ans; long long num; void Add(int x,int y) { next[++total] = head[x]; aim[total] = y; head[x] = total; ++_in[y]; from[y].push_back(x); } int MemorialSearch(int x) { if(memory[x] != -1) return memory[x]; int re = 0; for(vector<int>::iterator it = from[x].begin(); it != from[x].end(); ++it) if(f[*it] + ::cnt[x] == f[x]) re += MemorialSearch(*it),re %= p; return memory[x] = re; } void Solve() { static queue<int> q; memset(memory,-1,sizeof(memory)); for(int i = 1; i <= ::scc; ++i) if(!_in[i]) { q.push(i),f[i] = ::cnt[i]; memory[i] = 1; } while(!q.empty()) { int x = q.front(); q.pop(); for(int i = head[x]; i; i = next[i]) { f[aim[i]] = max(f[aim[i]],f[x] + ::cnt[aim[i]]); if(!--_in[aim[i]]) q.push(aim[i]); } } ans = *max_element(f + 1,f + ::scc + 1); for(int i = 1; i <= ::scc; ++i) if(f[i] == ans) num = (num + MemorialSearch(i)) % p; } } int main() { cin >> points >> edges >> p; for(int x,y,i = 1; i <= edges; ++i) { scanf("%d%d",&x,&y); Add(x,y); } for(int i = 1; i <= points; ++i) if(!dfn[i]) Tarjan(i); for(int x = 1; x <= points; ++x) for(int i = head[x]; i; i = next[i]) if(changed[x] != changed[aim[i]]) if(G.find(make_pair(changed[x],changed[aim[i]])) == G.end()) { DAG::Add(changed[x],changed[aim[i]]); G.insert(make_pair(changed[x],changed[aim[i]])); } DAG::Solve(); cout << DAG::ans << '\n' << DAG::num << endl; return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。