題目鏈接：http://acm.sgu.ru/problem.php?contest=0&problem=194
題意：
n 個點 m條有向邊
u v l r 代表該邊的流量區間為 [l,r]
若存在最大流則輸出每條邊的流量
若不存在則輸出NO
#include#include #include #include #include #include using namespace std; #define ll int #define N 10004 #define M 105000 #define inf 1073741824 #define inf64 1152921504606846976 struct Edge{ ll from, to, cap, nex, max; }edge[M*4];//注意這個一定要夠大 不然會re 還有反向弧 ll head[N], edgenum; void add(ll u, ll v, ll cap){ Edge E = { u, v, cap, head[u],cap}; edge[ edgenum ] = E; head[u] = edgenum ++; Edge E2= { v, u, 0, head[v],cap}; edge[ edgenum ] = E2; head[v] = edgenum ++; } ll sign[N]; bool BFS(ll from, ll to){ memset(sign, -1, sizeof(sign)); sign[from] = 0; queue q; q.push(from); while( !q.empty() ){ int u = q.front(); q.pop(); for(ll i = head[u]; i!=-1; i = edge[i].nex) { ll v = edge[i].to; if(sign[v]==-1 && edge[i].cap) { sign[v] = sign[u] + 1, q.push(v); if(sign[to] != -1)return true; } } } return false; } ll Stack[N], top, cur[N]; ll dinic(ll from, ll to){ ll ans = 0; while( BFS(from, to) ) { memcpy(cur, head, sizeof(head)); ll u = from; top = 0; while(1) { if(u == to) { ll flow = inf, loc;//loc 表示 Stack 中 cap 最小的邊 for(ll i = 0; i < top; i++) if(flow > edge[ Stack[i] ].cap) { flow = edge[Stack[i]].cap; loc = i; } for(ll i = 0; i < top; i++) { edge[ Stack[i] ].cap -= flow; edge[Stack[i]^1].cap += flow; } ans += flow; top = loc; u = edge[Stack[top]].from; } for(ll i = cur[u]; i!=-1; cur[u] = i = edge[i].nex)//cur[u] 表示u所在能增廣的邊的下標 if(edge[i].cap && (sign[u] + 1 == sign[ edge[i].to ]))break; if(cur[u] != -1) { Stack[top++] = cur[u]; u = edge[ cur[u] ].to; } else { if( top == 0 )break; sign[u] = -1; u = edge[ Stack[--top] ].from; } } } return ans; } void init(){memset(head,-1,sizeof head);edgenum = 0;} ll n, m; ll in[N], out[N], b[M]; int main(){ ll u, v, maxx, i, j; scanf("%d %d",&n, &m); init(); for(i = 0; i <= n+1; i++)in[i] = out[i] = 0; ll from = 0, to = n+1; for(i = 0; i < m; i++){ scanf("%d %d %d %d",&u,&v,&b[i],&maxx); add(u,v,maxx-b[i]); in[v] += b[i]; out[u]+= b[i]; } for(i = 1; i <= n; i++){ if(in[i] > out[i])add(from, i, in[i]-out[i]); else add(i, to, out[i]-in[i]); } dinic(from, to); bool yes = true; //源點的出邊必須滿流 for(i = head[from]; ~i; i = edge[i].nex) if(edge[i].cap)yes = false; //限制要相同 if(yes == false){puts("NO");return 0;} else puts("YES"); for(i = 0; i < m; i++){ ll ans = b[i] + (edge[i*2].max - edge[i*2].cap); printf("%lld\n",ans); } return 0; } /* 4 6 1 2 1 2 2 3 1 2 3 4 1 2 4 1 1 2 1 3 1 2 4 2 1 2 4 6 1 2 1 3 2 3 1 3 3 4 1 3 4 1 1 3 1 3 1 3 4 2 1 3 */
#include#include #include #include #include #include using namespace std; #define ll long long #define inf 123456789123456 #define MAXN N #define N 1000 #define M 100000 //N為點數 M為邊數 inline ll Min(ll a,ll b){return a>b?b:a;} //注意這個類型是int struct Edge{ ll from, to, cap, nex, max; }edge[M*2];//雙向邊，注意RE 注意這個模版是 相同起末點的邊 同時有效而不是去重 ll head[N],edgenum;//2個要初始化-1和0 void add(ll u, ll v, ll cap){//網絡流要加反向弧，即u->v 為10 則 v->u為 -10 Edge E = {u, v, cap, head[u],cap}; edge[ edgenum ] = E; head[ u ] = edgenum++; Edge E2 = {v, u, 0, head[v],cap}; //這裡的cap若是單向邊要為0 edge[ edgenum ] = E2; head[ v ] = edgenum++; } ll dis[N], cur[N];//dis[i]表示i點距離起點的距離 cur[i]表示i點所連接的邊中 正在考慮的邊 優化不再考慮已經用過的點 初始化為head bool vis[N]; bool BFS(ll Start,ll End){//跑一遍最短路 memset(vis,0,sizeof(vis)); memset(dis,-1,sizeof(dis)); queue Q; Q.push(Start); dis[Start]=0; vis[Start]=1; while(!Q.empty()) { ll u = Q.front(); Q.pop(); for(ll i = head[u]; i != -1; i = edge[i].nex){ Edge E = edge[i]; if( !vis[E.to] && E.cap > 0) { vis[ E.to ] = true; dis[ E.to ] = dis[ u ] + 1; if(E.to == End) return true; Q.push( E.to ); } } } return false; } ll DFS(ll x, ll a,ll End){//當前 流入x 的流量是a 流量a 是所有流過邊中 邊權的最小值 if( x == End || a == 0)return a; ll flow = 0, f; //flow表示從x點流到下面所有點，最大的流量 for(ll& i = cur[x]; i != -1; i = edge[i].nex) { Edge& E = edge[i]; if(dis[x] + 1 == dis[E.to] && (f = DFS(E.to , Min(a, E.cap), End))>0 ) { E.cap -= f; edge[ i^1 ].cap += f;//反向邊要減掉 flow += f; a -= f; if(a==0)break; } } return flow; } ll Maxflow(ll Start,ll End){ ll flow=0; while(BFS(Start,End)){ //當存在源點到匯點的路徑時 memcpy(cur,head,sizeof(head));//把head的數組復制過去 flow += DFS(Start, inf, End); } return flow; }/**/ void init(){memset(head,-1,sizeof head);edgenum = 0;} ll n, m; ll in[MAXN], out[MAXN], b[M]; ll s, t; int main(){ ll u, v, maxx, i, j; scanf("%lld %lld",&n, &m); init(); for(i = 0; i <= n+1; i++)in[i] = out[i] = 0; ll from = 0, to = n+1; s = from, t = to; for(i = 0; i < m; i++){ scanf("%lld %lld %lld %lld",&u,&v,&b[i],&maxx); add(u,v,maxx-b[i]); in[v] += b[i]; out[u]+= b[i]; } for(i = 1; i <= n; i++){ if(in[i] > out[i])add(from, i, in[i]-out[i]); else add(i, to, out[i]-in[i]); } Maxflow(from, to); bool yes = true; //源點的出邊必須滿流 for(i = head[from]; ~i; i = edge[i].nex) if(edge[i].cap)yes = false; //限制要相同 if(yes == false){puts("NO");return 0;} else puts("YES"); for(i = 0; i < m; i++){ ll ans = b[i] + (edge[i*2].max - edge[i*2].cap); printf("%lld\n",ans); } return 0; }
