记录编号	190327	评测结果	AAAAAAAAAA
题目名称	[SPOJ 839] 最优标号	最终得分	100
用户昵称	张灵犀不和我一般见识真可怕呢（笑	是否通过	通过
代码语言	C++	运行时间	0.127 s
提交时间	2015-10-02 22:19:55	内存使用	0.87 MiB

#include<cstdio>
#include<deque>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
const int SIZEN=510,SIZEM=3010,maxn=0x7fffffff/2;
typedef long long LL;
LL ans=0;
int N,M,tot=0,ma=0,K;
bool ok[SIZEN];
int H[SIZEN]={0};
LL e[SIZEN]={0};
LL P[SIZEN]={0},powr[SIZEN]={0};
deque<int> s[SIZEN],w[SIZEN],Q;
class miku
{
public:
	int fr,to,cap;
	miku(){}
	miku(int a,int b,int c)
	{
		fr=a,to=b,cap=c;
	}
}E[SIZEM*6];
void add(int fr,int to,int cap)
{
	if(fr==to) return;
	s[fr].push_back(tot);
	E[tot++]=miku(fr,to,cap);
	s[to].push_back(tot);
	E[tot++]=miku(to,fr,0);
}
LL min(int a,LL b)
{
	if(a<b) return a;
	else return b;
}
void read()
{
	scanf("%d%d",&N,&M);
	int u,v;
	for(int i=1;i<=M;i++)
	{
		scanf("%d%d",&u,&v);
		w[u].push_back(v);
		w[v].push_back(u);
	}
	scanf("%d",&K);
	int p;
	for(int i=1;i<=K;i++)
	{
		scanf("%d%d",&u,&p);
		ok[u]=1;P[u]=p;
		if(p>ma) ma=p;
	}
	for(int i=1;i<=N;i++) add(0,i,0),add(i,N+1,0);
}
void Pow(int a)
{
	powr[1]=1;
	for(int i=1;powr[i]<ma;i++)
	{
		powr[i+1]=powr[i]*2;
	}
}
void graph(int a)
{
	for(int i=1;i<=N;i++)
	{
		if(ok[i]==1)
		{
			if((P[i]&a)==0) add(0,i,maxn);
			else add(i,N+1,maxn);
		}
		for(int j=0;j<w[i].size();j++)
			add(i,w[i][j],1);
	}
}
void push(int x,int t)
{
	miku &v=E[t];
	LL flow=min(v.cap,e[x]);
	e[x]-=flow;v.cap-=flow;e[v.to]+=flow;E[t^1].cap+=flow;
	if(v.to!=0&&v.to!=N+1&&e[v.to]>0) Q.push_back(v.to);
}
void use_up(int x)
{
	int mi;
	while(e[x])
	{
		mi=maxn;
		//cout<<x<<" "<<"H[x]:"<<H[x]<<" "<<"e[x]"<<e[x]<<endl;
		for(int i=0;i<s[x].size();i++)
		{
			miku &v=E[s[x][i]];
			//cout<<"v.to:"<<v.to<<" "<<"v.cap:"<<v.cap<<" "<<"H[v.to]:"<<H[v.to]<<endl;
			if(v.cap<=0) continue;
			if(H[v.to]==H[x]-1)
			{
				//cout<<e[x]<<endl;
				push(x,s[x][i]);
				//cout<<e[x]<<endl;
				if(!e[x]) break;
			}
			else if(H[v.to]<mi) mi=H[v.to];
		}
		if(!e[x]) break;
		H[x]=mi+1;
	}
}
int maxflow()
{
	H[0]=N/2;e[0]=(LL)maxn*100;if(H[0]>10) H[0]=10;
	for(int i=0;i<s[0].size();i++) push(0,s[0][i]);
	while(!Q.empty())
	{
		int x=Q.front();Q.pop_front();
		//cout<<x<<endl;
		use_up(x);
	}
	return e[N+1];
}
void work()
{
	Pow(ma);
	for(int i=1;ma>0;ma>>=1,i++)
	{
		memset(H,0,sizeof(H));memset(e,0,sizeof(e));tot=0;
		for(int j=0;j<=N+1;j++) s[j].clear();
		graph(powr[i]);
		ans+=(maxflow()*powr[i]);
		//cout<<"ans:"<<ans<<endl;
		//cout<<"*****************"<<endl;
	}
	cout<<ans<<endl;
}
int main()
{
	freopen("optimalmarks.in","r",stdin);
	freopen("optimalmarks.out","w",stdout);
	read();
	work();
	return 0;
}