最小割。
CODE:
/*
AUTHOR: Su Jiao
DATE: 2010-7-20
DESCRIPTION:
网络流 乱做
http://www.spoj.pl/problems/OPTM/
*/
#include <stdio.h>
#include <string.h>
const int oo=(~0u)>>1;
const int MAXV=1000000;
const int MAXE=1000000;
typedef struct struct_edge* edge;
struct struct_edge{int v,c;edge n,b;};
struct_edge pool[MAXE];
edge top;
int S,T,V;
edge adj[MAXV];
int d[MAXV];
int q[MAXV];
int head,tail;
void add_edge(int u,int v,int c)
{
top->v=v,top->c=c,top->n=adj[u],adj[u]=top++;
top->v=u,top->c=0,top->n=adj[v],adj[v]=top++;
adj[u]->b=adj[v],adj[v]->b=adj[u];
}
bool relabel()
{
for (int i=0;i<V;d[i++]=oo) ;
d[q[head=tail=0]=T]=0;
while (head<=tail)
{
int u=q[head++];
for (edge i=adj[u];i;i=i->n)
if (i->b->c&&d[i->v]==oo)
d[q[++tail]=i->v]=d[u]+1;
if (d[S]!=oo) return true;
}
return false;
}
int augment(int u,int e)
{
if (u==T) return e;
int f=0;
for (edge i=adj[u];i&&e;i=i->n)
if (i->c&&d[u]==d[i->v]+1)
if (int df=augment(i->v,e<i->c?e:i->c))
i->c-=df,i->b->c+=df,e-=df,f+=df;
return f;
}
int dinic()
{
int f=0;
while (relabel()) f+=augment(S,oo);
return f;
}
const int SIZE=1000000;
int t;
int n,m,k;
int a[SIZE],b[SIZE],u[SIZE],p[SIZE],o[SIZE],visited[SIZE];
void dfs(int u,int length)
{
visited[u]=true;
o[u]|=1<<length;
for (edge i=adj[u];i;i=i->n)
if (i->c&&!visited[i->v]) dfs(i->v,length);
}
int main()
{
scanf(“%d”,&t);
for (int tt=0;tt<t;tt++)
{
scanf(“%d%d”,&n,&m);
for (int i=0;i<m;i++)
scanf(“%d%d”,a+i,b+i);
scanf(“%d”,&k);
for (int i=0;i<k;i++)
scanf(“%d%d”,u+i,p+i);
for (int i=1;i<=n;o[i++]=0) ;
for (unsigned int bit=1,length=0;bit;bit<<=1,length++)
{
top=pool;
for (int i=0;i<V;i++) visited[i]=int(adj[i]=0);
S=0,T=n+1,V=n+2;
for (int i=0;i<k;i++)
if (p[i]&bit) add_edge(S,u[i],oo);
else add_edge(u[i],T,oo);
for (int i=0;i<m;i++)
add_edge(a[i],b[i],1),add_edge(b[i],a[i],1);
dinic();
dfs(S,length);
}
for (int i=1;i<=n;i++) printf(“%d\n”,o[i]);
}
}