2095: [Poi2010]Bridges

本文主要是介绍2095: [Poi2010]Bridges，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

混合图的欧拉回路一般解法：
二分 + 最大流
先二分，然后判断该图是否能构成欧拉回路
考虑欧拉回路的成立条件，入度等于出度
也就是说，对于有向边，只用考虑其对入度出度的贡献，
然后对于无向边就要考虑其方向…
那么先任意规定无向边的方向，然后跑最大流。
在满足没有点出入度为0或出入度差为奇数（因为此时改变无向边的方向出入度之差变化为2）的前提下
如果能满流，那么就成立，否则不成立
考虑为何这样是对的。。。
实际上一开始无向边规定的那一个流量1，相当于跑了以后出入度变化量为2，
所以s ->i的流量为(out-in)/2,i ->t的流量为(in-out)/2
所以跑最大流的过程实际上是把边的方向重新改变.
c++代码如下：

#include<bits/stdc++.h>
#define rep(i,x,y) for(register int i = x ; i <= y; ++ i)
#define repd(i,x,y) for(register int i = x ; i >= y; -- i)
using namespace std;
typedef long long ll;
template<typename T>inline void read(T&x)
{x = 0;char c;int sign = 1;do { c = getchar(); if(c == '-') sign = -1; }while(!isdigit(c));do { x = x * 10 + c - '0'; c = getchar(); }while(isdigit(c));x *= sign;
}const int N = 1e3+50,M = 4e5+500,inf = 1e9+7;
struct Str { int u,v,c,d; }edge[M];
int cur[N],head[N],nxt[M],to[M],f[M],tot;
int n,m,s,t,ans,d[N],in[N],out[N];inline void add(int x,int y,int w)
{f[tot] = w;to[tot] = y;nxt[tot] = head[x];head[x] = tot ++;
}inline bool bfs()
{queue<int>q ;memset(d,0,sizeof d);q.push(s); d[s] = 1;while(!q.empty()){int x = q.front();q.pop();cur[x] = head[x];for(register int i = head[x];~i;i = nxt[i])if(!d[to[i]] && f[i]){d[to[i]] = d[x] + 1;q.push(to[i]);}}return d[t];
}int dfs(int x,int w)
{if(x == t || !w) return w;int F,flow = 0;for(register int&i=cur[x];~i;i=nxt[i])if(d[to[i]] == d[x] + 1 && ( F = dfs(to[i],min(f[i],w)))){f[i] -= F;f[i^1] += F;w -= F; flow += F;if(!w) break;}return flow;    
}inline bool check(int x)
{memset(in,0,sizeof in);memset(out,0,sizeof out);memset(head,-1,sizeof head);tot = 0;rep(i,1,m){if(edge[i].c <= x){out[edge[i].v]++; in[edge[i].u]++;}else return false;if(edge[i].d <= x){add(edge[i].v,edge[i].u,1);add(edge[i].u,edge[i].v,0);}}int sum = 0,ans = 0;rep(i,1,n)if((abs(in[i] - out[i]) & 1) || (!in[i] && !out[i]))return false;else if(out[i] - in[i] > 0){add(s,i,(out[i] - in[i]) / 2);add(i,s,0);sum += (out[i] - in[i]) / 2;}else if(in[i] - out[i] > 0){add(i,t,(in[i] - out[i]) / 2);add(t,i,0);}while(bfs())ans += dfs(s,inf);return ans == sum;
}int main()
{read(n); read(m);rep(i,1,m){read(edge[i].u); read(edge[i].v);read(edge[i].c); read(edge[i].d);if(edge[i].c > edge[i].d)swap(edge[i].c,edge[i].d),swap(edge[i].u,edge[i].v);}s = 0;t = n + 1;int l = 1,r = 1e4+50,mid; while(l <= r){if(check(mid = l + r >> 1)) ans = mid,r = mid - 1;else l = mid + 1;}if(ans ) cout << ans << '\n';else puts("NIE");return 0;
}

这篇关于2095: [Poi2010]Bridges的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---