题目链接
题解
题目大意：
给定下界,找出一种可行流方案
跑那么无上下界可行流
每条边在可行流中的流量=容量下界+附加流中它的流量
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using std::queue;
inline int read() {
int x=0;
char c=getchar();
while(c<'0'||c>'9') c=getchar();
while(c<='9'&&c>='0')x=x*10+c-'0',c=getchar();
return x;
}
const int maxn = 207;
const int maxm = 100007;
int head[maxn];
int minflow[maxm],flow[maxn];
struct node{
int next,num,v,flow;
}edge[maxm];
int n,m,num=1;
void add_edge(int u,int v,int flow,int N) {
edge[++num].v=v;edge[num].flow=flow,edge[num].next=head[u];head[u]=num,edge[num].num=N;
edge[++num].v=u,edge[num].flow=0;edge[num].next=head[v],head[v]=num,edge[num].num=N;
}
int S=0,T;
int dis[maxn],q[maxn];
int lev[maxn],cur[maxn];
bool bfs() {
memset(lev,-1,sizeof lev);
memcpy(cur,head,sizeof head);
queue<int>que;
lev[S]=0;
que.push(S);
while(!que.empty()) {
int u=que.front();que.pop();
for(int i=head[u];i;i=edge[i].next) {
int v=edge[i].v;
if(edge[i].flow>0&&lev[v]<0) {
lev[v]=lev[u]+1;
que.push(v);
}
}
}
if(lev[T]!=-1)return true;
else return false;
}
int dfs(int now,int flow) {
if(now==T)return flow;
int rest=0,delta;
for(int &i=cur[now];i;i=edge[i].next) {
int v=edge[i].v;
if(lev[v]==lev[now]+1&&edge[i].flow>0) {
delta=dfs(v,std::min(flow-rest,edge[i].flow));
if(delta) {
edge[i].flow-=delta;
edge[i^1].flow+=delta;
rest+=delta;if(rest==flow)break;
}
}
}
if(rest==flow)lev[now]=-1;
return rest;
}
int Dinic() {
int ret=0,tmp;
while(bfs()) {
ret+=dfs(S,0x3f3f3f3f);
}
return ret;
}
int ans[maxm];
void work() {
n=read(),m=read();T=n+1;
for(int a,b,c,i=1;i<=m;++i) {
a=read(),b=read(),minflow[i]=read(),c=read();
add_edge(a,b,c-minflow[i],i);
flow[a]-=minflow[i],flow[b]+=minflow[i];
}
int sum=0;
for(int i=1;i<=n;++i) {
if(flow[i]<0) add_edge(i,T,-flow[i],0);
else sum+=flow[i],add_edge(S,i,flow[i],0);
}
if(Dinic()==sum) {
puts("YES");
for(int i=1;i<=n;++i) {
for(int j=head[i];j;j=edge[j].next) {
if(j%2==0)continue;
ans[edge[j].num]=edge[j].flow+minflow[edge[j].num];
}
}
for(int i=1;i<=m;++i)printf("%d
",ans[i]);
}
else puts("NO");
}
int main() {
int Q=read();
for(;Q--;) {
memset(head,0,sizeof head);
memset(flow,0,sizeof(flow));
work();
}
return 0;
}