fisher最优分割法_最小二乘一定有最优解

全栈程序员-站长 • 2022年8月9日下午3:16 • 未分类 • 阅读 5

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元售后保障童叟无欺

给定一个无向图 G=(V,E)，每个顶点都有一个标号，它是一个 [0,231−1] 内的整数。

不同的顶点可能会有相同的标号。

对每条边 (u,v)，我们定义其费用 cost(u,v) 为 u 的标号与 v 的标号的异或值。

现在我们知道一些顶点的标号。

你需要确定余下顶点的标号使得所有边的费用和尽可能小。

输入格式
第一行有两个整数 N,M，N 是图的点数，M 是图的边数。

接下来有 M 行，每行有两个整数 u,v，代表一条连接 u,v 的边。

接下来有一个整数 K，代表已知标号的顶点个数。

接下来的 K 行每行有两个整数 u,p，代表点 u 的标号是 p。

假定这些 u 不会重复。

所有点编号从 1 到 N。

输出格式
输出一行一个整数，即最小的费用和。

数据范围
1≤N≤500,
0≤M≤3000,
1≤K≤N

输入样例：
3 2
1 2
2 3
2
1 5
3 100
输出样例：
97

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f;
const int N = 510;
const int M = 2 * (3000 + 500);
struct Edge{ 
   
    int v,w,next;
}edge[M];
int head[N],cnt;
int n,m,s,e;
int p[N];
void add(int u,int v,int w1,int w2){ 
   
    edge[cnt].v = v;
    edge[cnt].w = w1;
    edge[cnt].next = head[u];
    head[u] = cnt ++;
    edge[cnt].v = u;
    edge[cnt].w = w2;
    edge[cnt].next = head[v];
    head[v] = cnt ++;
}
int q[N],hh = 0,tt = 0,d[N],cur[N];
PII edges[M];
bool bfs(){ 
   
    hh = tt = 0;
    memset(d,-1,sizeof d);
    d[s] = 0,q[tt ++] = s,cur[s] = head[s];
    while(hh < tt){ 
   
        int t = q[hh ++];
        for(int i = head[t];~i;i = edge[i].next){ 
   
            int v = edge[i].v,w = edge[i].w;
            if(d[v] == -1 && w){ 
   
                d[v] = d[t] + 1;
                cur[v] = head[v];
                q[tt ++] = v;
                if(v == e)return true;
            }
        }
    }
    return false;
}
int dfs(int u,int limit){ 
   
    if(u == e)return limit;
    int flow = 0;
    for(int i = cur[u];~i && flow < limit;i = edge[i].next){ 
   
        int v = edge[i].v,w = edge[i].w;
        cur[u] = i;
        if(d[v] == d[u] + 1 && w){ 
   
            int t = dfs(v,min(w,limit - flow));
            if(!t)d[v] = -1;
            flow += t,edge[i].w -= t,edge[i ^ 1].w += t; 
        }
    }
    return flow;
}
void build(int k){ 
   
    memset(head,-1,sizeof head);
    cnt = 0;
    for(int i = 0;i < m;i ++){ 
   
        add(edges[i].x,edges[i].y,1,1);
    }
    for(int i = 1;i <= n;i ++){ 
   
        if(p[i] >= 0){ 
   
            if((p[i] >> k) & 1)add(i,e,INF,0);      //如果要让一个点属于某s或者t,只需要从s或者t连一条向口二道门的权值为INF的边即可
            else add(s,i,INF,0);
        }
    }
}
int dinic(int i){ 
   
    build(i);
    int maxflow = 0,flow = 0;
    while(bfs())while(flow = dfs(s,INF))maxflow += flow;
    return maxflow;
}
int main(){ 
   
    cin>>n>>m;
    for(int i = 0;i < m;i ++){ 
   
        scanf("%d %d",&edges[i].x, &edges[i].y);
    }
    int k,id,x;
    s = 0,e = n + 1;
    cin>>k;
    memset(p,-1,sizeof p);
    for(int i = 1;i <= k;i ++){ 
   
        scanf("%d %d",&id,&x);
        p[id] = x;
    }
    ll ans = 0;
    for(int i = 0;i <= 30;i ++){ 
   
        ans += ((ll)dinic(i) << i);
    }
    cout<<ans<<endl;
    return 0;
}