记录编号	95152	评测结果	AAAAAAAAAA
题目名称	[SPOJ 839] 最优标号	最终得分	100
用户昵称	Chenyao2333	是否通过	通过
代码语言	C++	运行时间	0.103 s
提交时间	2014-04-04 12:45:35	内存使用	0.35 MiB

#include<stdio.h>
#include<iostream>
#include<queue>
#include<algorithm>
#include<vector>
#include<string.h>

//1<=N<=500,0<=M<=3000
const int MAXN=500+10;
const int MAXM=3000+10;
const int MAXP=MAXN+100;
const int INF=10000*10000;

typedef long long LL;

int N,M,K;

using namespace std;

struct edge{
	int from,to,cap,flow;
};

struct dinic{
	int n,m,s,t;
	int cur[MAXP],d[MAXP];
	vector<int> G[MAXP];
	vector<edge> edges;
	bool inq[MAXP];
	
	void init(int s,int t){
		this->s=s;this->t=t;
		for(int i=0;i<MAXP;i++)G[i].clear();
		edges.clear();
	}
	
	void add_edge(int from,int to,int cap){
		//printf("from:%d to:%d cap:%d\n",from,to,cap);
		edges.push_back((edge){from,to,cap,0});
		edges.push_back((edge){to,from,0,0});
		m=edges.size();
		G[from].push_back(m-2);
		G[to].push_back(m-1);
	}
	
	bool BFS(){
		memset(d,0,sizeof(d));
		memset(inq,0,sizeof(inq));
		queue<int> q;
		q.push(s);inq[s]=true;
		while(!q.empty()){
			int u=q.front();q.pop();inq[u]=false;
			for(int i=0;i<G[u].size();i++){
				edge &e=edges[G[u][i]];
				if(e.cap>e.flow && d[e.to]==0 && e.to!=s){
					d[e.to]=d[u]+1;
					if(!inq[e.to]){
						inq[e.to]=true;
						q.push(e.to);
					}
				}
			}
		}
		return d[t];
	}
	
	int DFS(int u,int a){
		if(u==t || a==0)return a;
		int flow=0;
		for(int &i=cur[u];i<G[u].size();i++){
			edge &e=edges[G[u][i]];
			if(d[e.to]!=d[u]+1)continue;
			int f=DFS(e.to,min(a,e.cap-e.flow));
			//if(f==0) return flow;
			a-=f;
			flow+=f;
			edge &ee=edges[G[u][i]^1];
			e.flow+=f;
			ee.flow-=f;
			if(a==0)return flow;
		}
		return flow;
	}
	
	void test(){
		for(int i=0;i<edges.size();i++){
			edge &e=edges[i];
			printf("from:%d to:%d cap:%d flow:%d\n",e.from,e.to,e.cap,e.flow);
		}
		for(int i=0;i<=t;i++){
			printf("d[%d]:%d\n",i,d[i]);
		}
		printf("======================\n");
	}
	
	int max_flow(){
		int flow=0;
		while(BFS()){
			memset(cur,0,sizeof(cur));
			flow+=DFS(s,INF);
			//test();
		}
		return flow;
	}
	

}solver;

struct input{
	int a,b;
}inputs[MAXM+MAXN];

bool vis[MAXN]={0};

LL max_n=0;

void read(){
	scanf("%d %d",&N,&M);
	for(int i=1;i<=M;i++){
		int a,b;scanf("%d %d",&a,&b);
		if(a==b){
			i--;M--;
			continue;
		}
		input &in=inputs[i];
		in.a=a;in.b=b;
	}
	scanf("%d",&K);
	for(int i=1;i<=K;i++){
		int u=i+M;
		int a,b;scanf("%d %d",&a,&b);
		input &in=inputs[u];
		in.a=a;in.b=b;
		max_n=max(max_n,(LL)max(a,b));
	}
}

LL solve(){
	int s=0,t=N+1;
	solver.init(s,t);
	LL k=0;
	LL kk=1;
	LL ans=0;
	while((kk<=max_n)){

		solver.init(s,t);
		for(int i=1;i<=M;i++){
			input &in=inputs[i];
			solver.add_edge(in.a,in.b,1);
			solver.add_edge(in.b,in.a,1);
		}
		for(int i=M+1;i<=M+K;i++){
			input &in=inputs[i];
			if(in.b&kk){
				solver.add_edge(s,in.a,INF);
			}else{
				solver.add_edge(in.a,t,INF);
			}
		}
		ans+=solver.max_flow()*kk;
		kk*=2;
	}
	return ans;
}

void work(){
	read();
	LL ans=0;
	int cost=0;
	ans=solve();
	printf("%lld",ans);
}

void open(){
	//freopen("in.txt","r",stdin);
	freopen("optimalmarks.in","r",stdin);
	freopen("optimalmarks.out","w",stdout);
}

main(){
	open();
	work();
	return 0;
}