/*
结论1：有解的充要条件是所有点权之和为0
结论2：删掉环上的一条边，只要将这个环上的其余边都减去这条边的边权，那么这个图仍是等价的
从原图网络中构造出一棵带权值的树即可，其他边权都设置为0
通过dfs建立一棵搜索树 要注意处理边的方向
*/
#include<bits/stdc++.h>
using namespace std;
#define maxn 200005
struct Edge{
int to,nxt,w,d,id;}e[maxn<<
1];
int head[maxn],tot,n,m,a[maxn];
void init(){memset(head,-
1,
sizeof head);tot=
0;}
void add(
int u,
int v,
int id){
//方向，编号
e[tot].id=id;e[tot].to=v;e[tot].nxt=head[u];head[u]=tot++
;
}
int vis[maxn];
int dfs(
int u){
int res=a[u];vis[u]=
1;
for(
int i=head[u];i!=-
1;i=
e[i].nxt){
int v=
e[i].to;
if(vis[v])
continue;
int tmp=
dfs(v);
e[i].w=
tmp;
e[i^
1].w=-
tmp;
res+=
tmp;
}
return res;
}
int ans[maxn];
int main(){
cin>>
n;init();
for(
int i=
1;i<=n;i++)cin>>
a[i];
cin>>
m;
for(
int i=
1;i<=m;i++
){
int u,v;
scanf("%d%d",&u,&
v);
add(u,v,i);add(v,u,i);
}
if(dfs(
1)){puts(
"Impossible");
return 0;}
puts("Possible");
for(
int i=
0;i<tot;i+=
2)
ans[e[i].id]=
e[i].w;
for(
int i=
1;i<=m;i++
)
cout<<ans[i]<<
'\n';
}
转载于:https://www.cnblogs.com/zsben991126/p/11116136.html
