题目大意：
有一个有向无环图，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的路径上的点找出来，否则会使无用的点对结果产生影响。
代码：
1 #include<queue> 2 #include<vector> 3 #include<cstdio> 4 using namespace std; 5 const int N=1009,M=5009; 6 int cnt,n,m,i,x,y,h,t,a[M],b[M],v[M<<1],pre[N],last[M<<1],w[M<<1],head[N],dist[N],count[N]; 7 bool vis[N],mark[N],flag[N]; 8 vector <int> l[N],r[N]; 9 10 int read() 11 { 12 int x=0; 13 char ch=getchar(); 14 while (ch<'0' || ch>'9') ch=getchar(); 15 while (ch>='0' && ch<='9') x=(x<<1)+(x<<3)+ch-48,ch=getchar(); 16 return x; 17 } 18 19 void add(int x,int y,int z) 20 { 21 v[++cnt]=y,last[cnt]=head[x],head[x]=cnt,w[cnt]=z; 22 } 23 24 bool SPFA() 25 { 26 queue <int> q; 27 for (q.push(1),vis[1]=count[1]=1;!q.empty();) 28 for (x=q.front(),q.pop(),vis[x]=0,i=head[x];i;i=last[i]) 29 if (dist[y=v[i]]<w[i]+dist[x]) 30 { 31 dist[y]=dist[x]+w[i]; 32 if (!vis[y]) 33 { 34 q.push(y),vis[y]=1; 35 if (++count[y]>n) return 1; 36 } 37 } 38 return 0; 39 } 40 41 void wk1(int x) 42 { 43 int i; 44 for (flag[x]=1,i=0;i<l[x].size();i++) 45 if (!flag[l[x][i]]) wk1(l[x][i]); 46 } 47 48 void wk2(int x) 49 { 50 int i; 51 for (mark[x]=1,i=0;i<r[x].size();i++) 52 if (!mark[r[x][i]]) wk2(r[x][i]); 53 } 54 55 int main() 56 { 57 for (n=read(),m=read(),i=1;i<=m;i++) a[i]=read(),b[i]=read(); 58 for (i=1;i<=m;i++) l[a[i]].push_back(b[i]),r[b[i]].push_back(a[i]); 59 for (wk1(1),wk2(n),i=1;i<=n;i++) flag[i]&=mark[i]; 60 for (i=1;i<=m;i++) 61 if (flag[a[i]] && flag[b[i]]) add(a[i],b[i],1),add(b[i],a[i],-2); 62 if (SPFA()) puts("No"); 63 else 64 for (puts("Yes"),i=1;i<=m;i++) 65 if (flag[a[i]] && flag[b[i]]) printf("%d ",dist[b[i]]-dist[a[i]]); 66 else puts("1"); 67 return 0; 68 }