记录编号 277113 评测结果 AAAAAAAAAA
题目名称 1573.[SPOJ 839] 最优标号 最终得分 100
用户昵称 TenderRun 是否通过 通过
代码语言 C++ 运行时间 0.024 s
提交时间 2016-07-04 19:45:31 内存使用 0.92 MiB
显示代码纯文本
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
const int INF=1000000000;
const int maxn=1010;
const int maxm=30010;
int cnt,fir[maxn],to[maxm],nxt[maxm],cap[maxm];
void addedge(int a,int b,int c){
	nxt[++cnt]=fir[a];
	fir[a]=cnt;
	cap[cnt]=c;
	to[cnt]=b;
}

queue<int>q;
int dis[maxn];
bool BFS(int s,int t){
	dis[t]=1;q.push(t);
	while(!q.empty()){
		int x=q.front();q.pop();
		for(int i=fir[x];i;i=nxt[i])
			if(!dis[to[i]]){
				dis[to[i]]=dis[x]+1;
				q.push(to[i]);
			}
	}	
	return dis[s];
}

int fron[maxn];
int gap[maxn],path[maxn];
int ISAP(int s,int t){
	if(!BFS(s,t))return 0;
	for(int i=s;i<=t;i++)++gap[dis[i]];
	for(int i=s;i<=t;i++)fron[i]=fir[i];
	int p=s,ret=0,f;
	while(dis[s]<=t+1){
		if(p==t){
			f=INF;
			while(p!=s){
				f=min(f,cap[path[p]]);
				p=to[path[p]^1];				
			}
			ret+=f;p=t;
			while(p!=s){
				cap[path[p]]-=f;
				cap[path[p]^1]+=f;
				p=to[path[p]^1];
			}
		}
		int &ii=fron[p];
		for(;ii;ii=nxt[ii])
			if(cap[ii]&&dis[p]==dis[to[ii]]+1)
				break;
		if(ii)
			path[p=to[ii]]=ii;
		else{
			if(--gap[dis[p]]==0)break;
			int minn=t+1;
			for(int i=fir[p];i;i=nxt[i])
				if(cap[i])minn=min(minn,dis[to[i]]);
			++gap[dis[p]=minn+1];ii=fir[p];
			if(p!=s)p=to[path[p]^1];	
		}			
	}
	return ret;
}

void Init(){
	memset(fir,0,sizeof(fir));
	memset(dis,0,sizeof(dis));
	memset(gap,0,sizeof(gap));
	cnt=1;
}

int n,m,w[maxn];
int E[maxm][2],fa[maxn];
int Find(int x){
	return fa[x]==x?x:fa[x]=Find(fa[x]);
}
long long Solve(){
	int s=0,t=n+1;
	long long ret=0;
	for(int k=0;k<=30;k++){
		Init();
		for(int i=1;i<=n;i++)
			if(Find(i)==0&&w[i]!=-1){
				if(w[i]>>k&1){
					addedge(s,i,INF);
					addedge(i,s,0);
				}
				else{
					addedge(i,t,INF);
					addedge(t,i,0);
				}
			}
		for(int i=1;i<=m;i++)
			if(Find(E[i][0])==0){
				addedge(E[i][0],E[i][1],1);
				addedge(E[i][1],E[i][0],1);
			}
		ret+=(1ll<<k)*ISAP(s,t);
	}
	return ret;
}

int main(){
#ifndef ONLINE_JUDGE
	freopen("optimalmarks.in","r",stdin);
	freopen("optimalmarks.out","w",stdout);
#endif	
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
		for(int j=0;j<=1;j++)
			scanf("%d",&E[i][j]);
	
	int u,v,k;
	scanf("%d",&k);
	memset(w,-1,sizeof(w));
	while(k--){
		scanf("%d",&u);
		scanf("%d",&w[u]);
	}
	
	for(int i=1;i<=n;i++)
		fa[i]=w[i]==-1?0:i;
	
	for(int i=1;i<=m;i++){
		u=Find(E[i][0]);
		v=Find(E[i][1]);
		if(u>v)swap(u,v);
		if(u!=v)fa[v]=u;
	}
	printf("%lld\n",Solve());
	return 0;
}