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

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新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;
}