首页 > 代码库 > 【POJ1637】Sightseeing tour 混合图求欧拉回路存在性 网络流、
【POJ1637】Sightseeing tour 混合图求欧拉回路存在性 网络流、
题意:多组数据,最后的0/1表示0无向1有向。
问是否存在欧拉回路。
题解:无向边给它任意定个向。
首先欧拉回路中点入度=出度。
然后发现每个无向边如果修改个方向,原来的入点的入度+1,出度-1,出点反之。
然后我们不妨对入度和出度不同的点跟源汇中之一连边,容量为入出度差一半(每改一条边差-2)
然后原来的无向边联系图中各点,容量1,最后check if(maxflow==sum差/4)。
这都没看懂的弱菜们不妨出度多的连源,入度多的连汇,容量为入出度差一半,然后按无向边的定向给它在网络流图中定向,容量1。然后自己分析为什么要这么建(其实上面就是说明)。
1A代码:
#include <cmath> #include <queue> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define N 405 #define G 100000 #define inf 0x3f3f3f3f #define INF 0x3f3f3f3f3f3f3f3fll #define LL int using namespace std; struct KSD { int v,next,len; }e[G]; int head[N],cnt; void add(int u,int v,int len) { cnt++; e[cnt].v=v; e[cnt].len=len; e[cnt].next=head[u]; head[u]=cnt; } queue<int>q; int d[N],s,t; bool bfs() { memset(d,0,sizeof(d)); int i,u,v; while(!q.empty())q.pop(); q.push(s),d[s]=1; while(!q.empty()) { u=q.front(),q.pop(); for(i=head[u];i;i=e[i].next)if(e[i].len) { v=e[i].v; if(!d[v]) { d[v]=d[u]+1; if(v==t) return 1; q.push(v); } } } return 0; } int dinic(int x,int flow) { if(x==t)return flow; int remain=flow,k; int i,v; for(i=head[x];i&&remain;i=e[i].next) { v=e[i].v; if(e[i].len&&d[v]==d[x]+1) { k=dinic(v,min(remain,e[i].len)); if(!k)d[v]=0; e[i^1].len+=k,e[i].len-=k; remain-=k; } } return flow-remain; } int rd[N],od[N]; int n,m,sum,maxflow; void init() { cnt=1; sum=maxflow=0; s=n+1,t=n+2; memset(head,0,sizeof(head)); memset(rd,0,sizeof(rd)); memset(od,0,sizeof(od)); } void work() { int i,a,b,c; scanf("%d%d",&n,&m); init(); for(i=1;i<=m;i++) { scanf("%d%d%d",&a,&b,&c); rd[b]++,od[a]++; if(!c)add(a,b,1),add(b,a,0); } for(i=1;i<=n;i++) { if((rd[i]+od[i])&1) { puts("impossible"); return ; } sum+=abs(rd[i]-od[i]); if(od[i]>rd[i])add(s,i,od[i]-rd[i]>>1),add(i,s,0); else if(rd[i]>od[i]) add(i,t,rd[i]-od[i]>>1),add(t,i,0); } while(bfs())maxflow+=dinic(s,inf); if(maxflow*4==sum)puts("possible"); else puts("impossible"); } int main() { // freopen("test.in","r",stdin); int g;for(scanf("%d",&g);g--;)work(); }
【POJ1637】Sightseeing tour 混合图求欧拉回路存在性 网络流、
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。