终于知道什么是无源汇网络流的题了。。。

#include<iostream> #include<algorithm> #include<iostream> #include<stdio.h> #include<string.h> #include<stdlib.h> #include<vector> #include<queue> #include<cmath> using namespace std; #define ll long long #define inf 0x3f3f3f3f int dir[4][2]={0,1,-1,0}; int n,m; int c[305]; int lo[50000]; const int maxnode = 300 + 5; const int maxedge = 2*50000 + 5; const int oo = 1000000000; int node,src,dest,nedge; int head[maxnode],point[maxedge],next1[maxedge],flow[maxedge],capa[maxedge];//point[x]==y表示第x条边连接y，head，next为邻接表，flow[x]表示x边的动态值，capa[x]表示x边的初始值 int dist[maxnode],Q[maxnode],work[maxnode];//dist[i]表示i点的等级 void init(int _node,int _src,int _dest){//初始化，node表示点的个数，src表示起点，dest表示终点 node = _node; src = _src; dest = _dest; for (int i = 0; i < node; i++) head[i] = -1; nedge = 0; } void addedge(int u,int v,int c1,int c2){//增加一条u到v流量为c1，v到u流量为c2的两条边 point[nedge] = v,capa[nedge] = c1,flow[nedge] = 0,next1[nedge] = head[u],head[u] = (nedge++); point[nedge] = u,capa[nedge] = c2,next1[nedge] = head[v],head[v] = (nedge++); } bool dinic_bfs(){ memset(dist,255,sizeof (dist)); dist[src] = 0; int sizeQ = 0; Q[sizeQ++] = src; for (int cl = 0; cl < sizeQ; cl++) for (int k = Q[cl],i = head[k]; i >= 0; i = next1[i]) if (flow[i] < capa[i] && dist[point[i]] < 0){ dist[point[i]] = dist[k] + 1; Q[sizeQ++] = point[i]; } return dist[dest] >= 0; } int dinic_dfs(int x,int exp){ if (x == dest) return exp; for (int &i = work[x]; i >= 0; i = next1[i]){ int v = point[i],tmp; if (flow[i] < capa[i] && dist[v] == dist[x] + 1 && (tmp = dinic_dfs(v,min(exp,capa[i] - flow[i]))) > 0){ flow[i] += tmp; flow[i^1] -= tmp; return tmp; } } return 0; } int dinic_flow(){ int result = 0; while (dinic_bfs()){ for (int i = 0; i < node; i++) work[i] = head[i]; while (1){ int delta = dinic_dfs(src,oo); if (delta == 0) break; result += delta; } } return result; } //建图前,运行一遍init()； //加边时，运行addedge(a,b,c,0),表示点a到b流量为c的边建成（注意点序号要从0开始） //求解最大流运行dinic_flow(),返回值即为答案 int main() { while(scanf("%d%d",&n,&m)!=EOF) { int i,j; int ta,tb,tc,td,sum=0;; init(n+2,n+1); memset(c,sizeof(c)); for(i=1;i<=m;i++) { scanf("%d%d%d%d",&ta,&tb,&tc,&td); lo[i]=tc; addedge(ta,td-tc,0); c[ta]-=tc; c[tb]+=tc; } for(i=1;i<=n;i++) { if(c[i]>0) { addedge(0,i,c[i],0); sum+=c[i]; } else if(c[i]<0) addedge(i,n+1,-c[i],0); } int ans; ans=dinic_flow(); if(ans==sum) { printf("YES\n"); for(i=0;i<m;i++) printf("%d\n",flow[i*2]+lo[i+1]); } else printf("NO\n"); } return 0; }