题意:
给出一个图,每条边有一个流量。现在给出每个点要求的最终的流量大小,构造出一种流量方案。使得能够满足条件。如果无解输出Impossible
分析:
很容易证明一点:只要每个点的流量和为0,就一定有解。
证明很简单,设aiai表示i点的需求。如果存在两个点u,vu,v,au>0au>0,且av<0av<0那么可以找到一条从u到v的路径,每条边都正向流min(|au|,|av|)min(|au|,|av|)的流量,这样一来,中间的点没有任何影响,而这两个点的需求就改变了。
根据这种思路,很容易发现,我们只需要在图中找一颗树出来就行了,因为树就能够保证所有点之间均有唯一的路径。于是这道题就非常简单了:从叶节点开始向上处理,如果当前的点需要流进来,则其父亲向其流合适的流量,如果需要流出去,则反之。并且处理完当前点后,更新父亲的需求。即如果当前从父亲流过来一些,则父亲需要更多的流量,反之亦然。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#define SF scanf
#define PF printf
#define MAXN 200010
using namespace std;
vector<pair<int,int> > a[MAXN];
int n,val[MAXN],ans[MAXN],m,u,v;
bool vis[MAXN];
void dfs(int x,int fa,int id){vis[x]=1;for(int i=0;i<a[x].size();i++)if(vis[a[x][i].first]==0)dfs(a[x][i].first,x,a[x][i].second);if(val[x]!=0){if(id<0)ans[-id]-=val[x];elseans[id]+=val[x];val[fa]+=val[x];val[x]=0;}
}
int main(){SF("%d",&n);int sum=0;for(int i=1;i<=n;i++){SF("%d",&val[i]);sum+=val[i];}if(sum!=0){PF("Impossible");return 0;} PF("Possible\n");SF("%d",&m);for(int i=1;i<=m;i++){SF("%d%d",&u,&v); a[u].push_back(make_pair(v,i));a[v].push_back(make_pair(u,-i));}dfs(1,0,0);for(int i=1;i<=m;i++){PF("%d\n",ans[i]);}
}