[Poi2012]Festival 题解

[Poi2012]Festival

时间限制: 1 Sec 内存限制: 64 MB

题目描述

有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}大小的最大值。

输入

第一行三个正整数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)，表示第二类限制。

输出

一个正整数，表示集合{Xi}大小的最大值。

如果无解输出NIE。

样例输入

样例输出

提示

|X3=1, X1=X4=2, X2=3

这样答案为3。容易发现没有更大的方案。

　　先膜拜一下Q某犇，他给我讲的这道题。

　　这道题基本一看就是差分约束，建边已经是套路了，问题在于如何乱搞找出正解。首先，我们可以看出每一个强联通分量对答案的贡献与其他强联通分量无关，因为他们之间建边的话只能是某几个单向的0边，又因为Xi无限制，所以完全是可以对每个强联通分量单独结算在合并的。

　　那么我们怎么求在单个强联通分量的最大大小呢？floyd最长路就好了。反正n<=600这道题想卡你的话貌似也不太容易，因此我们大可将每个强联通分量中的点建一个链表，复杂度就大大降低了。

　　而有没有接嘛，只要看跑完floyd之后dis[i][i]是否为0就好了。

  1 #include<iostream>
  2 #include<cstdlib>
  3 #include<cstdio>
  4 #include<cstring>
  5 #include<algorithm>
  6 #include<map>
  7 #include<queue>
  8 #include<string>
  9 #include<cmath>
 10 #define N 750
 11 using namespace std;
 12 int n,m1,m2;
 13 int zz,dis[N][N];
 14 bool rz[N],rz2[N];
 15 int dfn[N],low[N],st[N],zz2,top;
 16 int be[N],zz3,pre[N];
 17 int mx[N];
 18 void tar(int x){
 19     zz2++;
 20     dfn[x]=low[x]=zz2;
 21     rz[x]=rz2[x]=1;
 22     top++;
 23     st[top]=x;
 24     for(int i=1;i<=n;i++)
 25     {
 26         if(dis[x][i]!=dis[0][0]&&i!=x)
 27         {
 28             if(!rz2[i])
 29             {
 30                 tar(i);
 31                 low[x]=min(low[x],low[i]);
 32             }
 33             else if(rz[i])
 34             {
 35                 low[x]=min(low[x],dfn[i]);
 36             }
 37         }
 38     }
 39     if(low[x]==dfn[x])
 40     {
 41         zz3++;
 42         int v,la=0;
 43         do{
 44             v=st[top];
 45             top--;
 46             rz[v]=0;
 47             if(!be[zz3])
 48                 be[zz3]=v;
 49             pre[la]=v;
 50             la=v;
 51         }while(dfn[v]!=low[v]);
 52     }
 53 }
 54 int main(){
 55     memset(pre,-1,sizeof(pre));
 56     scanf("%d%d%d",&n,&m1,&m2);
 57     memset(dis,-0xf,sizeof(dis));
 58     for(int i=1;i<=m1;i++)
 59     {
 60         int x,y;
 61         scanf("%d%d",&x,&y);
 62         dis[x][y]=max(dis[x][y],1);
 63         dis[y][x]=max(-1,dis[y][x]);
 64     }
 65     for(int i=1;i<=m2;i++)
 66     {
 67         int x,y;
 68         scanf("%d%d",&x,&y);
 69         dis[x][y]=max(dis[x][y],0);
 70     }
 71     for(int i=1;i<=n;i++)
 72     {
 73         if(!rz2[i])
 74         {
 75             tar(i);
 76         }
 77     }
 78        
 79     for(int i=1;i<=n;i++)
 80     {
 81         dis[i][i]=0;
 82     }
 83     for(int o=1;o<=zz3;o++)
 84     {
 85         for(int k=be[o];k!=-1;k=pre[k])
 86         {
 87             for(int i=be[o];i!=-1;i=pre[i])
 88             {
 89                 for(int j=be[o];j!=-1;j=pre[j])
 90                 {
 91                     if(abs(dis[i][k])<=n&&abs(dis[k][j])<=n)
 92                         dis[i][j]=max(dis[i][j],dis[i][k]+dis[k][j]);
 93                 }
 94             }
 95         }
 96         for(int i=be[o];i!=-1;i=pre[i])
 97         {
 98             for(int j=be[o];j!=-1;j=pre[j])
 99                 mx[o]=max(mx[o],abs(dis[i][j]));
100         }
101     }
102     for(int i=1;i<=n;i++)
103     {
104         if(dis[i][i]!=0)
105         {
106             printf("NIE
");
107             exit(0);
108         }
109     }
110       
111     int ans=0;
112     for(int i=1;i<=zz3;i++)
113         ans+=mx[i]+1;
114     printf("%d
",ans);
115    // while(1);
116     return 0;
117 }
118

View Code