CodeForces - 241E Flights 题解

题目大意：

　　有一个有向无环图，n个点m条边，所有边权为1或2，求一组使所有从1到n的路径长度相同的边权的方案。

思路：

　　设从1到i的最短路为dist[i]，若有一条从x到y的边，则1<=dist[y]-dist[x]<=2，即dist[y]-dist[x]>=1且dist[x]-dist[y]>=-2，有了这个约束条件，就可以跑差分约束了。不过跑之前要先把从1到n的路径上的点找出来，否则会使无用的点对结果产生影响。

代码：

 #include<queue>

 #include<vector>

 #include<cstdio>

 using namespace std;

 const int N=,M=;

 int cnt,n,m,i,x,y,h,t,a[M],b[M],v[M<<],pre[N],last[M<<],w[M<<],head[N],dist[N],count[N];

 bool vis[N],mark[N],flag[N];

 vector <int> l[N],r[N];

 int read()

 {

     int x=;

     char ch=getchar();

     while (ch<'' || ch>'') ch=getchar();

     while (ch>='' && ch<='') x=(x<<)+(x<<)+ch-,ch=getchar();

     return x;

 }

 void add(int x,int y,int z)

 {

     v[++cnt]=y,last[cnt]=head[x],head[x]=cnt,w[cnt]=z;

 }

 bool SPFA()

 {

     queue <int> q;

     for (q.push(),vis[]=count[]=;!q.empty();)

         for (x=q.front(),q.pop(),vis[x]=,i=head[x];i;i=last[i])

             if (dist[y=v[i]]<w[i]+dist[x])

             {

                 dist[y]=dist[x]+w[i];

                 if (!vis[y])

                 {

                     q.push(y),vis[y]=;

                     if (++count[y]>n) return ;

                 }

             }

     return ;

 }

 void wk1(int x)

 {

     int i;

     for (flag[x]=,i=;i<l[x].size();i++)

         if (!flag[l[x][i]]) wk1(l[x][i]);

 }

 void wk2(int x)

 {

     int i;

     for (mark[x]=,i=;i<r[x].size();i++)

         if (!mark[r[x][i]]) wk2(r[x][i]);

 }

 int main()

 {

     for (n=read(),m=read(),i=;i<=m;i++) a[i]=read(),b[i]=read();

     for (i=;i<=m;i++) l[a[i]].push_back(b[i]),r[b[i]].push_back(a[i]);

     for (wk1(),wk2(n),i=;i<=n;i++) flag[i]&=mark[i];

     for (i=;i<=m;i++)

         if (flag[a[i]] && flag[b[i]]) add(a[i],b[i],),add(b[i],a[i],-);

     if (SPFA()) puts("No");

     else

         for (puts("Yes"),i=;i<=m;i++)

             if (flag[a[i]] && flag[b[i]]) printf("%d\n",dist[b[i]]-dist[a[i]]);

             else puts("");

     return ;

 }

巴特西

CodeForces - 241E Flights 题解

最新文章

热门文章