大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新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;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/169078.html原文链接：https://javaforall.net
