记录编号	378622	评测结果	AAAAAAAAAA
题目名称	[SPOJ 839] 最优标号	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.055 s
提交时间	2017-03-04 13:30:11	内存使用	5.65 MiB

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long ll;
const int N=1e5+10;
struct edge{int f,t;ll g;}w[N];
int S,T,n,m,k,head[N],next[N],cnt,a[N],b[N],v[N];
void add(int f,int t,ll g){
	w[++cnt]=(edge){f,t,g};
	next[cnt]=head[f];
	head[f]=cnt;
	w[++cnt]=(edge){t,f,g};
	next[cnt]=head[t];
	head[t]=cnt;
}
int t[32];
void init(int bit){
	for (int i=1;i<=cnt;i++) next[i]=0;
	for (int i=S;i<=T;i++) head[i]=0;
	cnt=1;
	for (int i=1;i<=m;i++) add(a[i],b[i],t[bit]);
	for (int i=1;i<=n;i++)
		if (v[i]!=-1) v[i]&t[bit]?add(S,i,1e16):add(i,T,1e16);
}
struct st{
	int x,i;ll df;
	st(int X=0,ll DF=0){x=X;i=head[x];df=DF;}
}z[N];
int top,l[N];ll ans;
#define V z[top].x
#define E z[top].i
#define F z[top].df
void change(){
	ll df=F;ans+=F;
	for (int i=top-1;i;i--){
		w[z[i].i].g-=df;
		w[z[i].i^1].g+=df;
		z[i].df-=df;
		if (!z[i].df) top=i;
	}
}
queue<int> Q;
void bfs(){
	for (int i=S;i<=T;i++) l[i]=0;
	l[S]=1;Q.push(S);
	while (!Q.empty()){
		int v=Q.front();Q.pop();
		if (l[T]) continue;
		for (int i=head[v];i;i=next[i])
		if (w[i].g&&!l[w[i].t])
			l[w[i].t]=l[v]+1,Q.push(w[i].t);
	}
}
bool dinic(){
	bfs();
	if (!l[T]) return 0;
	z[top=1]=st(S,1e16);
	while (top){
		if (V==T){change();top--;E=next[E];}else
		if (!E){l[V]=0;top--;E=next[E];}else
		if (w[E].g&&l[w[E].t]==l[V]+1)
			z[top+1]=st(w[E].t,min(w[E].g,F)),top++;
		else E=next[E];
	}
	return 1;
}
int main()
{
	freopen("optimalmarks.in","r",stdin);
	freopen("optimalmarks.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (int i=1;i<=m;i++) scanf("%d%d",&a[i],&b[i]);
	for (int i=1;i<=n;i++) v[i]=-1;
	scanf("%d",&k);
	for (int i=1;i<=k;i++){
		int u;
		scanf("%d",&u);
		scanf("%d",&v[u]);
	}
	S=0;T=n+1;
	for (int i=0;i<31;i++){
		t[i]=1<<i;
		init(i);
		while (dinic());
	}
	printf("%lld\n",ans);
	return 0;
}