题目链接：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 ==