传送门:acdream 1211
给定n个点,以及它们之间的m个管道,每个管道有流量的最小限制和最大限制,问能否存在一种情况,使得所有管道内的流量都满足流量限制
带上下界的网络流,如果不考虑流量的最小限制,那就是单纯的网络流问题,因此这里只需要转化一下即可。
对于每一条管道,将最小限制加到入口的出度,加到出口的入度,求出所有点的总入度与总出度,总入度大的,建立一个源点指向该点,流量即为该点入度与出度之差,总出度大的,该点建一条边指向一个汇点,流量为出度与入度之差,然后每条管道的流量限制都更新为最@R_224_403@与最小流量之差,对于建立的新图跑一遍网络流,如果是汇源满流则说明可行,每条管道的流量即为新图的当前流量与该管道的最小流量限制之和。
- /******************************************************
- * File Name: b.cpp
- * Author: kojimai
- * Creater Time:2014年10月01日 星期三 16时00分06秒
- ******************************************************/
- #include<cstdio>
- #include<cstring>
- #include<queue>
- #include<cmath>
- #include<algorithm>
- #include<iostream>
- using namespace std;
- #define FFF 205
- int first[FFF],in[FFF],e,dis[FFF];
- struct node
- {
- int v,f,l,next;
- }edge[50005];
- void addedge(int x,int y,int l,int c)
- {
- edge[e].v=y;edge[e].next=first[x];edge[e].l=l;edge[e].f=c;first[x]=e++;
- edge[e].v=x;edge[e].next=first[y];edge[e].l=0;edge[e].f=0;first[y]=e++;
- }
- bool bfs(int s,int t)
- {
- memset(dis,-1,sizeof(dis));
- dis[s] = 0;
- queue<int> q;
- q.push(s);
- while(!q.empty())
- {
- int now = q.front();q.pop();
- for(int k = first[now];k!=-1;k = edge[k].next)
- {
- if(edge[k].f-edge[k].l>0 && dis[edge[k].v] ==-1)
- {
- dis[edge[k].v] = dis[now] + 1;
- if(edge[k].v == t)
- return true;
- q.push(edge[k].v);
- }
- }
- }
- return false;
- }
- int dfs(int now,int flow,int t)
- {
- int f;
- if(now == t)
- return flow;
- for(int k = first[now];k != -1;k = edge[k].next)
- {
- if(edge[k].f - edge[k].l > 0 && dis[edge[k].v] == dis[now] + 1 && (f=dfs(edge[k].v,min(flow,edge[k].f - edge[k].l),t)))
- {
- edge[k].f -= f;
- edge[k^1].f += f;
- return f;
- }
- }
- return 0;
- }
- int dinic(int s,int t)
- {
- int flow,ret = 0;
- while(bfs(s,t))
- {
- while(flow=dfs(s,233333333,t))
- ret += flow;
- }
- return ret;
- }
- int main()
- {
- int n,m,x,y,c;
- while(~scanf("%d%d",&n,&m))
- {
- memset(first,sizeof(first));
- memset(in,sizeof(in));
- e=0;
- for(int i=0;i<m;i++)
- {
- scanf("%d%d%d%d",&x,&y,&l,&c);
- addedge(x,c);
- in[x]-=l;in[y]+=l;
- }
- int sum = 0;
- for(int i=1;i<=n;i++)
- {
- if(in[i]>0)
- {
- addedge(0,i,in[i]);
- sum += in[i];
- }
- else if(in[i]<0)
- addedge(i,n+1,-in[i]);
- }
- int ans = dinic(0,n+1);
- if(sum == ans)
- {
- printf("YES\n");
- for(int i=0;i<m;i++)
- printf("%d\n",edge[i*2].l+edge[i*2+1].f);
- }
- else
- printf("NO\n");
- }
- return 0;
- }