2788: [Poi2012]Festival
Time Limit: 30 Sec Memory Limit: 64 MBSubmit: 187 Solved: 91
[Submit][Status][Discuss]
Description
有n个正整数X1,X2,...,Xn，再给出m1+m2个限制条件，限制分为两类：
1. 给出a,b (1<=a,b<=n)，要求满足Xa + 1 = Xb
2. 给出c,d (1<=c,d<=n)，要求满足Xc <= Xd
在满足所有限制的条件下，求集合{Xi}大小的最大值。
Input
第一行三个正整数n, m1, m2 (2<=n<=600, 1<=m1+m2<=100,000)。
接下来m1行每行两个正整数a,b (1<=a,b<=n)，表示第一类限制。
接下来m2行每行两个正整数c,d (1<=c,d<=n)，表示第二类限制。
Output
一个正整数，表示集合{Xi}大小的最大值。
如果无解输出NIE。
Sample Input
4 2 2
1 2
3 4
1 4
3 1
1 2
3 4
1 4
3 1
Sample Output
3
HINT
|X3=1, X1=X4=2, X2=3
这样答案为3。容易发现没有更大的方案。
Source
此题显然是个差分约束系统，先建好图。
如果两个点不是强连通的，显然这两个点不会互相影响。
所以先tarjan缩点，如果不在一个强连通块里的不会有影响，所以只需要考虑同意连通块内的点。
求元素不同的最大值等价于连通块内的最长路+1，由于数据范围较小，floyd即可。
如果存在正环，则 无解。
1 #include<cstdio> 2 #include<algorithm> 3 #define N 605 4 #define M 500010 5 using namespace std; 6 int head[N],dfn[N],belong[N],low[N],scc; 7 int map[N][N],q[N],top,tot,n,m1,m2,id,ans; 8 bool vis[N]; 9 struct edge{int next,to;}e[M]; 10 #define add(u,v) e[++tot]=(edge){head[u],v},head[u]=tot 11 void tarjan(int x) 12 { 13 low[x]=dfn[x]=++id; 14 q[++top]=x;vis[x]=1; 15 for(int i=head[x];i;i=e[i].next) 16 if(!dfn[e[i].to]) 17 tarjan(e[i].to),low[x]=min(low[x],low[e[i].to]); 18 else if(vis[e[i].to]) 19 low[x]=min(low[x],dfn[e[i].to]); 20 int now=0; 21 if(low[x]==dfn[x]) 22 { 23 scc++; 24 while(now!=x) 25 { 26 now=q[top--]; 27 belong[now]=scc; 28 vis[now]=0; 29 } 30 } 31 } 32 int main() 33 { 34 scanf("%d%d%d",&n,&m1,&m2); 35 for(int i=1;i<=n;i++) 36 for(int j=1;j<=n;j++) 37 if(i!=j)map[i][j]=-1e9; 38 else map[i][j]=0; 39 int x,y; 40 while(m1--) 41 { 42 scanf("%d%d",&x,&y); 43 add(x,y); 44 add(y,x); 45 map[x][y]=max(map[x][y],1); 46 map[y][x]=max(map[y][x],-1); 47 } 48 while(m2--) 49 { 50 scanf("%d%d",&x,&y); 51 add(x,y); 52 map[x][y]=max(map[x][y],0); 53 } 54 for(int i=1;i<=n;i++) 55 if(!dfn[i])tarjan(i); 56 for(int p=1;p<=scc;p++) 57 { 58 for(int k=1;k<=n;k++)if(belong[k]==p) 59 for(int i=1;i<=n;i++)if(belong[i]==p) 60 if(map[i][k]!=-1e9) 61 for(int j=1;j<=n;j++)if(belong[j]==p) 62 if(map[k][j]!=-1e9) 63 map[i][j]=max(map[i][j],map[i][k]+map[k][j]); 64 int now=0; 65 for(int i=1;i<=n;i++)if(belong[i]==p) 66 for(int j=1;j<=n;j++)if(belong[j]==p) 67 now=max(now,abs(map[i][j])); 68 ans+=now+1; 69 } 70 for(int i=1;i<=n;i++) 71 if(map[i][i]!=0) 72 return puts("NIE"),0; 73 printf("%d",ans); 74 }