图论（网络流）：SPOJ OPTM - Optimal Marks

37 阅读 0 评论 25 点赞

我是靠谱客的博主迷人画笔，最近开发中收集的这篇文章主要介绍图论（网络流）：SPOJ OPTM - Optimal Marks，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

OPTM - Optimal Marks

You are given an undirected graph G(V, E). Each vertex has a mark which is an integer from the range [0..2³¹ – 1]. Different vertexes may have the same mark.

For an edge (u, v), we define Cost(u, v) = mark[u] xor mark[v].

Now we know the marks of some certain nodes. You have to determine the marks of other nodes so that the total cost of edges is as small as possible.

Input

The first line of the input data contains integer T (1 ≤ T ≤ 10) - the number of testcases. Then the descriptions of T testcases follow.

First line of each testcase contains 2 integers N and M (0 < N <= 500, 0 <= M <= 3000). N is the number of vertexes and M is the number of edges. Then M lines describing edges follow, each of them contains two integers u, v representing an edge connecting u and v.

Then an integer K, representing the number of nodes whose mark is known. The next K lines contain 2 integers u and p each, meaning that node u has a mark p. It’s guaranteed that nodes won’t duplicate in this part.

Output

For each testcase you should print N lines integer the output. The Kth line contains an integer number representing the mark of node K. If there are several solutions, you have to output the one which minimize the sum of marks. If there are several solutions, just output any of them.

Example

Input:
1
3 2
1 2
2 3
2
1 5
3 100
Output:
5
4
100 

　　COGS上AC了，这里花46分钟买了个教训。
　　SPOJ:


1 #include <iostream>

2 #include <cstring>

3 #include <cstdio>

4 #include <queue>

5 using namespace std;

6 const int INF=1000000000;

7 const int maxn=1010;

8 const int maxm=30010;

9 int cnt,fir[maxn],to[maxm],nxt[maxm],cap[maxm];
 10 void addedge(int a,int b,int c){
 11
nxt[++cnt]=fir[a];
 12
fir[a]=cnt;
 13
cap[cnt]=c;
 14
to[cnt]=b;
 15 }
 16
 17 queue<int>q;
 18 int dis[maxn];
 19 bool BFS(int s,int t){
 20
dis[t]=1;q.push(t);
 21
while(!q.empty()){
 22
int x=q.front();q.pop();
 23
for(int i=fir[x];i;i=nxt[i])
 24
if(!dis[to[i]]){
 25
dis[to[i]]=dis[x]+1;
 26 
q.push(to[i]);
 27 
}
 28 
}
 29
return dis[s];
 30 }
 31
 32 int fron[maxn];
 33 int gap[maxn],path[maxn];
 34 int ISAP(int s,int t){
 35
if(!BFS(s,t))return 0;
 36
for(int i=s;i<=t;i++)++gap[dis[i]];
 37
for(int i=s;i<=t;i++)fron[i]=fir[i];
 38
int p=s,ret=0,f;
 39
while(dis[s]<=t+10){
 40
if(p==t){
 41
f=INF;
 42
while(p!=s){
 43
f=min(f,cap[path[p]]);
 44
p=to[path[p]^1];
 45 
}
 46
ret+=f;p=t;
 47
while(p!=s){
 48
cap[path[p]]-=f;
 49
cap[path[p]^1]+=f;
 50
p=to[path[p]^1];
 51 
}
 52 
}
 53
int &ii=fron[p];
 54
for(;ii;ii=nxt[ii])
 55
if(cap[ii]&&dis[p]==dis[to[ii]]+1)
 56
break;
 57
if(ii)
 58
path[p=to[ii]]=ii;
 59
else{
 60
if(--gap[dis[p]]==0)break;
 61
int minn=t+1;
 62
for(int i=fir[p];i;i=nxt[i])
 63
if(cap[i])minn=min(minn,dis[to[i]]);
 64
++gap[dis[p]=minn+1];ii=fir[p];
 65
if(p!=s)p=to[path[p]^1];
 66 
}
 67 
}
 68
return ret;
 69 }
 70
 71 void Init(){
 72
memset(fir,0,sizeof(fir));
 73
memset(dis,0,sizeof(dis));
 74
memset(gap,0,sizeof(gap));
 75
cnt=1;
 76 }
 77
 78 int n,m,T;
 79 long long a[maxn],w[maxn];
 80 int E[maxm][2],fa[maxn];
 81 int Find(int x){
 82
return fa[x]==x?x:fa[x]=Find(fa[x]);
 83 }
 84
 85 int vis[maxn];
 86 void DFS(int x,int d){
 87
vis[x]=1;a[x]|=d;
 88
for(int i=fir[x];i;i=nxt[i])
 89
if(cap[i]&&!vis[to[i]])
 90 
DFS(to[i],d);
 91 }
 92
 93 long long Solve(){
 94
int s=0,t=n+1;
 95
long long ret=0;
 96
for(int k=0;k<=30;k++){
 97 
Init();
 98
for(int i=1;i<=n;i++)
 99
if(Find(i)==0&&w[i]>=0){
100
if(w[i]>>k&1){
101 
addedge(s,i,INF);
102
addedge(i,s,0);
103 
}
104
else{
105 
addedge(i,t,INF);
106
addedge(t,i,0);
107 
}
108 
}
109
for(int i=1;i<=m;i++)
110
if(Find(E[i][0])==0){
111
addedge(E[i][0],E[i][1],1);
112
addedge(E[i][1],E[i][0],1);
113 
}
114
ret+=(1ll<<k)*ISAP(s,t);
115
memset(vis,0,sizeof(vis));
116
DFS(s,1ll<<k);
117 
}
118
return ret;
119 }
120
121 int main(){
122
scanf("%d",&T);
123
while(T--){
124
scanf("%d%d",&n,&m);
125
for(int i=1;i<=m;i++)
126
for(int j=0;j<=1;j++)
127
scanf("%d",&E[i][j]);
128
129
int u,v,k;
130
scanf("%d",&k);
131
memset(w,-1,sizeof(w));
132
memset(a,0,sizeof(a));
133
while(k--){
134
scanf("%d",&u);
135
scanf("%lld",&w[u]);
136 
}
137
138
for(int i=1;i<=n;i++)
139
fa[i]=w[i]!=-1?0:i;
140
141
for(int i=1;i<=m;i++){
142
u=Find(E[i][0]);
143
v=Find(E[i][1]);
144
if(u>v)swap(u,v);
145
if(u!=v)fa[v]=u;
146 
}
147 
Solve();
148
for(int i=1;i<=n;i++)
149
if(w[i]<0)
150
printf("%lldn",a[i]);
151
else
152
printf("%lldn",w[i]);
153 
}
154
return 0;
155 }