题目大意：给定一个无向图，，一些点有点权，一些点的点权可以自己指定，每条边的边权为两端点权值的异或，求边权最小值
按位拆开，每一位跑最小割
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define M 550#define S 0#define T (M-1)#define INF 0x3f3f3f3fusing namespace std;struct edge{int x,y;}edges[3030];int n,m,p;int a[M];long long ans;namespace Max_Flow{struct abcd{int to,f,next;}table[1001001];int head[M],tot=1;int dpt[M];void Initialize(){memset(head,0,sizeof head);tot=1;}void Add(int x,int y,int z){table[++tot].to=y;table[tot].f=z;table[tot].next=head[x];head[x]=tot;}void Link(int x,int y,int z){Add(x,y,z);Add(y,x,z);}bool BFS(){static int q[M];int i,r=0,h=0;memset(dpt,-1,sizeof dpt);q[++r]=S;dpt[S]=1;while(r!=h){int x=q[++h];for(i=head[x];i;i=table[i].next)if(table[i].f&&!~dpt[table[i].to]){dpt[table[i].to]=dpt[x]+1;q[++r]=table[i].to;if(table[i].to==T)return true;}}return false;}int Dinic(int x,int flow){int i,left=flow;if(x==T) return flow;for(i=head[x];i&&left;i=table[i].next)if(table[i].f&&dpt[table[i].to]==dpt[x]+1){int temp=Dinic(table[i].to,min(left,table[i].f) );left-=temp;table[i].f-=temp;table[i^1].f+=temp;}if(left) dpt[x]=-1;return flow-left;}}int main(){using namespace Max_Flow;int i,j,x,y;cin>>n>>m>>p;for(i=1;i<=m;i++){scanf("%d%d",&x,&y);edges[i].x=x;edges[i].y=y;}memset(a,-1,sizeof a);for(j=1;j<=p;j++){scanf("%d%d",&x,&y);a[x]=y;}for(j=0;j<=30;j++){Initialize();for(i=1;i<=n;i++)if(~a[i]){if( ~(a[i]>>j)&1 )Link(S,i,INF);elseLink(i,T,INF);}for(i=1;i<=m;i++)Link(edges[i].x,edges[i].y,1);while( BFS() )ans+=(long long)Dinic(S,INF)<<j;}cout<<ans<<endl;return 0;}
不给自己一点轻松的机会，好象世界的每个角落都需要自己的脚去留个痕迹，才叫人生。
