题意：

给出一张图，点有点权，边有边权

定义一条边的权值为其连接两点的异或和

定义一张图的权值为所有边的权值之和

已知部分点的点权，自定义其余点的点权

使图的权值最小，并在此基础上使点权和最小

输出点的权值

 

异或——按位做

那么题目就变成了已知一些点的点权为0/1，自定义剩余点的点权0/1

使01相遇的边最少

（01相遇指的是一条边连接的两点的点权不同）

我们建立最小割模型：

先不考虑第二问

源点向已知点的点权为0的点连正无穷的边

已知点的点权为1的点向汇点连正无穷的边

然后把原图加进去，原图中若存在u和v之间的边，就加入u向v，v向u 流量为1的边

这样最小割割的时候只会割流量为1的边，割一条边表示这条边连接的两点点权不同

最后在残量网络上，点与源点相连则代表点权为0，点与汇点相连代表点权为1

再来考虑第二问

第二问相当于最后残量网络上，点既可以与源点连又可以与汇点连的时候，选择与源点连

将所有不与源点相连的点x，加上源点向x流量为1的边

这样如果x最后选择与汇点相连，那么它就要多花费1的代价

这就使x尽可能的与源点相连

那么这岂不是影响了第一问的答案？

用点儿小技巧

原来是原图中若存在u和v之间的边，就加入u向v，v向u 流量为1的边

改成 原图中若存在u和v之间的边，就加入u向v，v向u 流量为10000的边

然后第一问相当于最最小割/10000

第二问相当于最小割%10000

 

最后查询与源点分离的点时，不是源点连出去的流量为1的边满流

而是dinic最后一次分层遍历遍历不到的点

S->2的边虽然满流，但是仍可以通过S->3->2 所以2是与源点相连的点

 

 

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;#define N 502#define M 3001const int inf=1e9;struct node{    int u,v;}e[3001];int num[N];int ans[N];int front[N],to[M*6],nxt[M*6],cap[M*6],tot;int src,decc;int lev[N],cur[N];queue
         
          q;void read(int &x){    x=0; char c=getchar();    while(!isdigit(c)) c=getchar();    while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }}void add(int u,int v,int w){    to[++tot]=v; nxt[tot]=front[u]; front[u]=tot; cap[tot]=w;    to[++tot]=u; nxt[tot]=front[v]; front[v]=tot; cap[tot]=0;}bool bfs(){    for(int i=src;i<=decc;++i) lev[i]=-1,cur[i]=front[i];    while(!q.empty()) q.pop();    q.push(src);    lev[src]=0;    int now;    while(!q.empty())    {        now=q.front();        q.pop();        for(int i=front[now];i;i=nxt[i])            if(cap[i] && lev[to[i]]==-1)            {                lev[to[i]]=lev[now]+1;                if(to[i]==decc) return true;                q.push(to[i]);            }    }    return false;}int dinic(int now,int flow){    if(now==decc) return flow;    int rest=0,delta;    for(int &i=cur[now];i;i=nxt[i])        if(cap[i] && lev[to[i]]>lev[now])        {            delta=dinic(to[i],min(flow-rest,cap[i]));            if(delta)            {                rest+=delta;                 cap[i]-=delta; cap[i^1]+=delta;                if(rest==flow) break;            }        }    if(rest!=flow) lev[now]=-1;    return rest;}int main(){    int T,n,m,k,x;//    int flow;//    long long ans1,ans2;    read(T);    while(T--)    {        memset(num,-1,sizeof(num));        memset(ans,0,sizeof(ans));        //ans1=ans2=0;        tot=1;        read(n); read(m);        for(int i=1;i<=m;++i) read(e[i].u),read(e[i].v);        read(k);        for(int i=1;i<=k;++i)        {            read(x);            read(num[x]);        }        decc=n+1;        for(int bit=0;bit<31;++bit)        {            memset(front,0,sizeof(front));            tot=1;            for(int i=1;i<=n;++i)                if(num[i]!=-1)                {                    if(num[i]&1<