首页 > 代码库 > SPOJ 839 Optimal Marks 最小割 经典 按位建图
SPOJ 839 Optimal Marks 最小割 经典 按位建图
胡伯涛论文中的一题,经典建模,由于二进制每一位异或不会相互影响,所以我们把问题转换模型,按位处理。
即已知一些点的标号0/1(还有些可以自己任意改),和一些边,边权定义为两端点标号的异或,要求边权和最小的标号方案。
我们联想到最小割求的是从源到汇容量最小的边权和。
建图:
标号为1的和源点相连,容量INF,标号为0的和汇点相连,容量INF,这些边是不能割掉的(这些点标号已经明确)
原图相连的边,连边,容量为1。(若将此边割掉,则两端点一个为0,一个为1,割为1)
跑完最大流后,在残量网络中dfs寻找S集合,也就是这些点都属于1.
#include<cstdio> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> #include<set> #include<map> #include<queue> #include<vector> #include<string> #define eps 1e-12 #define INF 0x7fffffff #define maxn 22222 using namespace std; int n,m,k; int en; int st,ed; int dis[maxn]; int que[9999999]; int cur[maxn]; struct edge { int to,c,next; }; edge e[9999999]; int head[maxn]; void add(int a,int b,int c) { e[en].to=b; e[en].c=c; e[en].next=head[a]; head[a]=en++; e[en].to=a; e[en].c=0; e[en].next=head[b]; head[b]=en++; } int bfs() { memset(dis,-1,sizeof(dis)); dis[st]=0; int front=0,rear=0; que[rear++]=st; while(front<rear) { int j=que[front++]; for(int k=head[j];k!=-1;k=e[k].next) { int i=e[k].to; if(dis[i]==-1&&e[k].c) { dis[i] = dis[j]+ 1 ; que[rear++]=i; if(i==ed) return true; } } } return false; } int dfs(int x,int mx) { if(x==ed || mx==0) return mx; int f,flow=0; for(int& i=cur[x];i!=-1;i=e[i].next) { if(dis[x]+1==dis[e[i].to] && (f=dfs(e[i].to,min(mx,e[i].c)))) { e[i].c-=f; e[i^1].c+=f; flow+=f; mx-=f; if(!mx)break; } } return flow; } void init() { en=0; st=0; ed=n+1; memset(head,-1,sizeof(head)); } int dinic() { int tmp=0; int maxflow=0; while(bfs()) { for(int i=st;i<=ed;i++) cur[i]=head[i]; while(tmp=dfs(st,INF)) maxflow+=tmp; } return maxflow; } bool mp[505][505],vis[505]; int mark[505]; int id[505]; void p(int a,int b,int w) { printf("%d->%d = %d\n",a,b,w); } void build(int move) { for(int i=1;i<=k;i++) { if((1<<move)&mark[id[i]]) { add(st,id[i],INF); } else { add(id[i],ed,INF); } } for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(mp[i][j]) { add(i,j,1); } } } } void get(int now,int move) { vis[now]=1; mark[now]|=(1<<move); for(int i=head[now];~i;i=e[i].next) if(e[i].c&&!vis[e[i].to]) get(e[i].to,move); } int main() { int cas,a,b; scanf("%d",&cas); while(cas--) { scanf("%d%d",&n,&m); memset(mark,0,sizeof(mark)); memset(mp,0,sizeof(mp)); for(int i=1;i<=m;i++) { scanf("%d%d",&a,&b); mp[a][b]=1; mp[b][a]=1; } scanf("%d",&k); for(int i=1;i<=k;i++) { scanf("%d%d",&a,&b); mark[a]=b; id[i]=a; } for(int i=0;i<=31;i++) { init(); build(i); dinic(); memset(vis,0,sizeof(vis)); get(st,i); } for(int i=1;i<=n;i++) { printf("%d\n",mark[i]); } } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。