CF241E Flights 题解

做了一下这道题，突然发现自己忘了差分约束，赶紧复习一下。

设当前有n个变量 a₁,a₂,...,a_n ，有若干组限制形如 a_i≤a_j+k (其中k为常数)，则由点j向点i连一条边权为k的边，再从某一确定的变量出发跑最短路(如若a₁=0，则设dis₁=0，从点1出发跑最短路)，得到的dis_i即为a_i的最大值。类似的，若把上面的小于等于改成大于等于，跑最长路，就可以得到每个点的最小值。若跑最短路时出现了负环（最长路正环），则说明无解。

代码：

  1     #include<bits/stdc++.h>
  2     using namespace std;
  3     #define N 200007
  4     int h1[N],pre[N],to[N],num,dis[N],h2[N],h3[N],w[N],f[N],n,m;
  5     int id[N],ans[N];
  6     bool tag1[N],tag2[N],tag[N],vis[N];
  7     queue<int> q;
  8     void add1(int x,int y,int z)
  9     {
 10         num++;pre[num]=h1[x];h1[x]=num;to[num]=y;id[num]=z;
 11     }
 12     void add2(int x,int y)
 13     {
 14         num++;pre[num]=h2[x];h2[x]=num;to[num]=y;
 15     }
 16     void add3(int x,int y,int z)
 17     {
 18         num++;pre[num]=h3[x];h3[x]=num;to[num]=y;w[num]=z;
 19     }
 20     bool spfa(int s)
 21     {
 22         int v,i,u;
 23         memset(dis,0x3f,sizeof(dis));
 24         memset(vis,0,sizeof(vis));
 25         dis[s]=0;f[s]=0;
 26         q.push(s);
 27         while(!q.empty())
 28         {
 29             v=q.front();q.pop();
 30             vis[v]=false;
 31             for(i=h3[v];i;i=pre[i])
 32             {
 33                 u=to[i];
 34                 if(dis[v]+w[i]<dis[u])
 35                 {
 36                     dis[u]=dis[v]+w[i];
 37                     f[u]=f[v]+1;
 38                     if(f[u]>=n+1)return false;
 39                     if(!vis[u])
 40                     {
 41                         q.push(u);
 42                         vis[u]=true;
 43                     }
 44                 }
 45             }
 46         }
 47         return true;
 48     }
 49     void dfs1(int v)
 50     {
 51         int i,u;
 52         tag1[v]=true;
 53         for(i=h1[v];i;i=pre[i])
 54         {
 55             u=to[i];
 56             if(tag1[u])continue;
 57             dfs1(u);
 58         }
 59     }
 60     void dfs2(int v)
 61     {
 62         int i,u;
 63         tag2[v]=true;
 64         for(i=h2[v];i;i=pre[i])
 65         {
 66             u=to[i];
 67             if(tag2[u])continue;
 68             dfs2(u);
 69         }
 70     }
 71     int main()
 72     {
 73         int i,x,y,j,u,v;
 74         scanf("%d%d",&n,&m);
 75         for(i=1;i<=m;i++)
 76         {
 77             scanf("%d%d",&x,&y);
 78             add1(x,y,i),add2(y,x);
 79         }
 80         dfs1(1),dfs2(n);
 81         for(i=1;i<=n;i++)
 82             if(tag1[i]&&tag2[i])
 83                 tag[i]=true;
 84         for(v=1;v<=n;v++)
 85             for(i=h1[v];i;i=pre[i])
 86             {
 87                 u=to[i];
 88                 if(tag[v]&&tag[u])
 89                 {
 90                     add3(v,u,-1);
 91                     add3(u,v,2);
 92                 }
 93             }
 94         if(!spfa(n))printf("No
");
 95         else
 96         {
 97             printf("Yes
");
 98             for(v=1;v<=n;v++)
 99                 for(i=h1[v];i;i=pre[i])
100                 {
101                     u=to[i];
102                     if(tag[u]&&tag[v])ans[id[i]]=dis[v]-dis[u];
103                     else ans[id[i]]=1;
104                 }
105             for(i=1;i<=m;i++)
106                 printf("%d
",ans[i]);
107         }
108         return 0;
109     }