rt,为什么cut[u]=i
是对的,cur[u]=e[i].nxt
就是错的啊/kel
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
struct edge
{
int v,w,nxt;
}e[20805];
struct node
{
int u,v,minw,maxw;
}E[10205];
int h[205],dis[205],cur[205],in[205],out[205],n,m,s,t,ans,cnt,sum;
void add(int u,int v,int w)
{
e[cnt].v=v;
e[cnt].w=w;
e[cnt].nxt=h[u];
h[u]=cnt++;
}
bool bfs()
{
for(int i=1;i<=n+2;i++)dis[i]=-1;
dis[s]=0;
queue<int>q;
q.push(s);
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=h[u];i!=-1;i=e[i].nxt)
{
int v=e[i].v;
if(dis[v]==-1&&e[i].w)
{
dis[v]=dis[u]+1;
q.push(v);
}
}
}
return dis[t]!=-1;
}
int dfs(int u,int flow)
{
if(u==t)return flow;
int rest=flow;
for(int i=cur[u];i!=-1;i=e[i].nxt)
{
cur[u]=i;//这是对的
//cur[u]=e[i].nxt 这是错的
int v=e[i].v;
if(dis[v]==dis[u]+1&&e[i].w)
{
int d=dfs(v,min(rest,e[i].w));
e[i].w-=d;e[i^1].w+=d;
rest-=d;
if(!rest)break;
}
}
return flow-rest;
}
signed main()
{
scanf("%d%d",&n,&m);
memset(h,-1,sizeof(h));
s=n+1;t=n+2;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d%d",&E[i].u,&E[i].v,&E[i].minw,&E[i].maxw);
in[E[i].v]+=E[i].minw;
out[E[i].u]+=E[i].minw;
add(E[i].u,E[i].v,E[i].maxw-E[i].minw);
add(E[i].v,E[i].u,0);
}
for(int i=1;i<=n;i++)
{
if(in[i]>=out[i])
{
add(s,i,in[i]-out[i]);
add(i,s,0);
sum+=in[i]-out[i];
}
else
{
add(i,t,out[i]-in[i]);
add(t,i,0);
}
}
while(bfs())
{
for(int i=1;i<=n+2;i++)cur[i]=h[i];
ans+=dfs(s,inf);
}
if(ans!=sum)printf("NO");
else
{
printf("YES\n");
for(int i=1;i<=2*m;i+=2)printf("%d\n",E[i/2+1].minw+e[i].w);
}
return 0;
}