记录编号	94503	评测结果	AAAAAAAAAA
题目名称	[SPOJ 839] 最优标号	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.273 s
提交时间	2014-04-01 16:07:56	内存使用	1.57 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
typedef long long ll;
const int SIZEN=510,INF=0x7fffffff/2;
class EDGE{
public:
	int from,to,cap,flow;
};
vector<EDGE>  edges;
vector<int> c[SIZEN];
int id[SIZEN][SIZEN]={0};
bool connected[SIZEN][SIZEN]={0};
int depth[SIZEN]={0},cur[SIZEN]={0};
int N,S,T;//0~N
void addedge(int from,int to,int cap){
	edges.push_back((EDGE){from,to,cap,0});
	edges.push_back((EDGE){to,from,0,0});
	int tot=edges.size()-2;
	c[from].push_back(tot);
	c[to].push_back(tot+1);
	id[from][to]=tot;//,id[to][from]=tot+1;
}
bool BFS(void){
	bool visit[SIZEN]={0};
	queue<int> Q;
	Q.push(S);
	depth[S]=0;visit[S]=true;
	while(!Q.empty()){
		int x=Q.front();Q.pop();
		for(int i=0;i<c[x].size();i++){
			EDGE &now=edges[c[x][i]];
			if(!visit[now.to]&&now.cap>now.flow){
				visit[now.to]=true;
				depth[now.to]=depth[x]+1;
				Q.push(now.to);
			}
		}
	}
	return visit[T];
}
int DFS(int x,int a){//节点x,剩余流量a可分
	if(x==T||!a) return a;
	int flow=0,cf;//flow是当前已送出的流量
	for(int i=cur[x];i<c[x].size();i++){
		EDGE &now=edges[c[x][i]];
		if(depth[now.to]==depth[x]+1){
			cf=DFS(now.to,min(a,now.cap-now.flow));
			if(cf){
				flow+=cf;
				a-=cf;
				edges[c[x][i]].flow+=cf,edges[c[x][i]^1].flow-=cf;
				if(!a){
					cur[x]=i+1;
					break;
				}
			}
		}
	}
	if(!flow) depth[x]=-1;//没有成功把a里面的任何流量送走,那么以后也就送不走了
	return flow;
}
int Dinic(void){
	int flow=0;
	while(BFS()){
		memset(cur,0,sizeof(cur));
		flow+=DFS(S,INF);
	}
	return flow;
}
int n,m,K;
pair<int,int> pred[SIZEN];
void rebuild(int k){//考虑第k位,建立和S,T有关的边
	for(int i=0;i<edges.size();i++) edges[i].flow=0;
	for(int i=1;i<=n;i++){//和S,T有关的边清空
		edges[id[S][i]].cap=0;
		edges[id[i][T]].cap=0;
	}
	for(int i=1;i<=K;i++){
		int u=pred[i].first,w=pred[i].second;
		w=((w>>(k-1))&1);
		if(w) edges[id[S][u]].cap=INF;//按1的往S连,因为要最小化下标和......英语拙计
		else edges[id[u][T]].cap=INF;
	}
}
bool visit[SIZEN]={0};
int ans[SIZEN]={0};
void DFS(int x){
	if(visit[x]) return;
	visit[x]=true;
	for(int i=0;i<c[x].size();i++){
		EDGE &now=edges[c[x][i]];
		if(now.flow>=now.cap) continue;
		DFS(now.to);
	}
}
ll costsum=0;
void test(int k){
	rebuild(k);
	costsum+=Dinic()*(ll)(1<<(k-1));
	memset(visit,0,sizeof(visit));
	DFS(S);
	for(int i=1;i<=n;i++){
		if(visit[i]) ans[i]=ans[i]*2+1;
		else ans[i]=ans[i]*2;
	}
}
void work(void){
	costsum=0;
	for(int i=31;i>=1;i--) test(i);
	printf("%lld\n",costsum);
	//for(int i=1;i<=n;i++) printf("%d\n",ans[i]);
}
void read(void){
	edges.clear();
	memset(id,0,sizeof(id));
	memset(ans,0,sizeof(ans));
	memset(pred,0,sizeof(pred));
	memset(connected,0,sizeof(connected));
	scanf("%d%d",&n,&m);
	N=n+1;S=0;T=N;
	for(int i=0;i<=N;i++) c[i].clear();
	int a,b;
	for(int i=1;i<=m;i++){
		scanf("%d%d",&a,&b);//这是可以被在割集中划分的
		addedge(a,b,1);
		addedge(b,a,1);
		connected[a][b]=connected[b][a]=true;
	}
	scanf("%d",&K);
	for(int i=1;i<=K;i++) scanf("%d%d",&pred[i].first,&pred[i].second);
	for(int i=1;i<=n;i++) addedge(S,i,0),addedge(i,T,0);//先建上,以后改权值
}
int main(){
	freopen("optimalmarks.in","r",stdin);
	freopen("optimalmarks.out","w",stdout);
	read();
	work();
	//下面是多组数据的内容
	/*int T;
	scanf("%d",&T);
	while(T--){
		read();
		work();
	}*/
	return 0;
}