首页 > 代码库 > 【BZOJ】1093: [ZJOI2007]最大半连通子图(tarjan+拓扑序)
【BZOJ】1093: [ZJOI2007]最大半连通子图(tarjan+拓扑序)
http://www.lydsy.com/JudgeOnline/problem.php?id=1093
两个条件综合起来加上求最大的节点数,那么很明显如果是环一定要缩点。
然后再仔细思考下就是求dag的最长路的数目啦。。。
然后wa了。。。
看了题解。。。噗!第一次注意到缩点后会有重边QAQ。。。于是。。
orz orz
然后思考了下怎么处理重边。。。很简单,每个点bfs时记录一下就行了。。
#include <cstdio>#include <cstring>#include <cmath>#include <string>#include <iostream>#include <algorithm>#include <queue>#include <set>#include <map>using namespace std;typedef long long ll;#define pii pair<int, int>#define mkpii make_pair<int, int>#define pdi pair<double, int>#define mkpdi make_pair<double, int>#define pli pair<ll, int>#define mkpli make_pair<ll, int>#define rep(i, n) for(int i=0; i<(n); ++i)#define for1(i,a,n) for(int i=(a);i<=(n);++i)#define for2(i,a,n) for(int i=(a);i<(n);++i)#define for3(i,a,n) for(int i=(a);i>=(n);--i)#define for4(i,a,n) for(int i=(a);i>(n);--i)#define CC(i,a) memset(i,a,sizeof(i))#define read(a) a=getint()#define print(a) printf("%d", a)#define dbg(x) cout << (#x) << " = " << (x) << endl#define error(x) (!(x)?puts("error"):0)#define printarr2(a, b, c) for1(_, 1, b) { for1(__, 1, c) cout << a[_][__]; cout << endl; }#define printarr1(a, b) for1(_, 1, b) cout << a[_] << ‘\t‘; cout << endlinline const int getint() { int r=0, k=1; char c=getchar(); for(; c<‘0‘||c>‘9‘; c=getchar()) if(c==‘-‘) k=-1; for(; c>=‘0‘&&c<=‘9‘; c=getchar()) r=r*10+c-‘0‘; return k*r; }inline const int max(const int &a, const int &b) { return a>b?a:b; }inline const int min(const int &a, const int &b) { return a<b?a:b; }#define rdm(x,i) for(int i=ihead[x]; i; i=e[i].next)const int N=100005, M=1000005;int TT, FF[N], LL[N], vis[N], s[N], top, scc, p[N], w[N], MD, ans1, ans2, in[N], front, tail;struct Gr { int ihead[N], n, cnt; struct dat { int next, to; }e[M]; void add(int u, int v) { e[++cnt].next=ihead[u]; ihead[u]=cnt; e[cnt].to=v; ++in[v]; } void dfs(int x) { FF[x]=LL[x]=++TT; vis[x]=1; s[++top]=x; rdm(x, i) { int y=e[i].to; if(!FF[y]) { dfs(y); LL[x]=min(LL[x], LL[y]); } else if(vis[y]) LL[x]=min(LL[x], FF[y]); } if(FF[x]==LL[x]) { ++scc; int y; do { y=s[top--]; vis[y]=0; p[y]=scc; w[scc]++; } while(x!=y); } } void tarjan() { for1(i, 1, n) if(!FF[i]) dfs(i); } void bfs() { int *d=FF, *f=LL, *q=s; for1(i, 1, n) d[i]=f[i]=vis[i]=0; front=tail=0; for1(i, 1, n) if(!in[i]) q[tail++]=i, d[i]=w[i], f[i]=1; while(front!=tail) { int u=q[front++]; if(front==N) front=0; rdm(u, i) { int v=e[i].to; if(!(--in[v])) { q[tail++]=v; if(tail==N) tail=0; } if(vis[v]) continue; if(d[v]==d[u]+w[v]) { f[v]=(f[v]+f[u])%MD; } else if(d[v]<d[u]+w[v]) { d[v]=d[u]+w[v]; f[v]=f[u]; } vis[v]=1; } rdm(u, i) vis[e[i].to]=0; } ans1=-1; for1(i, 1, n) ans1=max(ans1, d[i]); for1(i, 1, n) if(ans1==d[i]) ans2=(ans2+f[i])%MD; }}G, g;void build() { for1(i, 1, g.n) in[i]=0; G.n=scc; for1(x, 1, g.n) for(int i=g.ihead[x]; i; i=g.e[i].next) if(p[x]!=p[g.e[i].to]) G.add(p[x], p[g.e[i].to]);}int main() { read(g.n); int m=getint(); read(MD); for1(i, 1, m) { int u=getint(), v=getint(); g.add(u, v); } g.tarjan(); build(); G.bfs(); printf("%d\n%d\n", ans1, ans2); return 0;}
Description
Input
第一行包含两个整数N,M,X。N,M分别表示图G的点数与边数,X的意义如上文所述。接下来M行,每行两个正整数a, b,表示一条有向边(a, b)。图中的每个点将编号为1,2,3…N,保证输入中同一个(a,b)不会出现两次。
Output
应包含两行,第一行包含一个整数K。第二行包含整数C Mod X.
Sample Input
6 6 20070603
1 2
2 1
1 3
2 4
5 6
6 4
1 2
2 1
1 3
2 4
5 6
6 4
Sample Output
3
3
3
HINT
对于100%的数据, N ≤100000, M ≤1000000;对于100%的数据, X ≤10^8。
Source
【BZOJ】1093: [ZJOI2007]最大半连通子图(tarjan+拓扑序)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。