首页 > 代码库 > BZOJ2095: [Poi2010]Bridges
BZOJ2095: [Poi2010]Bridges
题解：
二分答案之后就是混合图（有向边+无向边）的欧拉回路问题。
如何判断欧拉回路是否存在？
把该图的无向边随便定向，计算每个点的入度和出度。如果有某个点出入度
之差为奇数，那么肯定不存在欧拉回路。因为欧拉回路要求每点入度 = 出度，
也就是总度数为偶数，存在奇数度点必不能有欧拉回路。
好了，现在每个点入度和出度之差均为偶数。那么将这个偶数除以 2，得 x。
也就是说，对于每一个点，只要将 x 条边改变方向（入>出就是变入，出>入就是9
变出），就能保证出=入。如果每个点都是出=入，那么很明显，该图就存在欧拉
回路。
现在的问题就变成了：我该改变哪些边，可以让每个点出=入？构造网络流
模型。首先，有向边是不能改变方向的，要之无用，删。一开始不是把无向边定
向了吗？定的是什么向，就把网络构建成什么样，边长容量上限 1。另新建 s 和
t。对于入>出的点 u，连接边(u, t)、容量为 x，对于出>入的点 v，连接边(s, v)，
容量为 x（注意对不同的点 x 不同）。之后，察看是否有满流的分配。有就是能
有欧拉回路，没有就是没有。欧拉回路是哪个？察看流值分配，将所有流量非 0
（上限是 1，流值不是 0 就是 1）的边反向，就能得到每点入度=出度的欧拉图。
由于是满流，所以每个入>出的点，都有 x 条边进来，将这些进来的边反向，
OK，入=出了。对于出>入的点亦然。那么，没和 s、t 连接的点怎么办？和 s 连
接的条件是出>入，和 t 连接的条件是入>出，那么这个既没和 s 也没和 t 连接的
点，自然早在开始就已经满足入=出了。那么在网络流过程中，这些点属于“中
间点”。我们知道中间点流量不允许有累积的，这样，进去多少就出来多少，反
向之后，自然仍保持平衡。
所以，就这样，混合图欧拉回路问题，解了。
代码：
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #include<set> 10 #include<queue> 11 #include<string> 12 #define inf 1000000000 13 #define maxn 100000+5 14 #define maxm 100000+5 15 #define eps 1e-10 16 #define ll long long 17 #define pa pair<int,int> 18 #define for0(i,n) for(int i=0;i<=(n);i++) 19 #define for1(i,n) for(int i=1;i<=(n);i++) 20 #define for2(i,x,y) for(int i=(x);i<=(y);i++) 21 #define for3(i,x,y) for(int i=(x);i>=(y);i--) 22 #define for4(i,x) for(int i=head[x],y=e[i].go;i;i=e[i].next,y=e[i].go) 23 #define mod 1000000007 24 using namespace std; 25 inline int read() 26 { 27 int x=0,f=1;char ch=getchar(); 28 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 29 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();} 30 return x*f; 31 } 32 int n,m,s,t,maxflow,tot=1,head[maxn],cur[maxn],h[maxn]; 33 queue<int>q; 34 bool can[maxn]; 35 int u[maxn],v[maxn],w1[maxn],w2[maxn],in[maxn],out[maxn],sum; 36 struct edge{int go,next,v;}e[maxm]; 37 void add(int x,int y,int v) 38 { 39 e[++tot]=(edge){y,head[x],v};head[x]=tot; 40 e[++tot]=(edge){x,head[y],0};head[y]=tot; 41 } 42 bool bfs() 43 { 44 for(int i=s;i<=t;i++)h[i]=-1; 45 q.push(s);h[s]=0; 46 while(!q.empty()) 47 { 48 int x=q.front();q.pop(); 49 for(int i=head[x];i;i=e[i].next) 50 if(e[i].v&&h[e[i].go]==-1) 51 { 52 h[e[i].go]=h[x]+1;q.push(e[i].go); 53 } 54 } 55 return h[t]!=-1; 56 } 57 int dfs(int x,int f) 58 { 59 if(x==t) return f; 60 int tmp,used=0; 61 for(int i=cur[x];i;i=e[i].next) 62 if(e[i].v&&h[e[i].go]==h[x]+1) 63 { 64 tmp=dfs(e[i].go,min(e[i].v,f-used)); 65 e[i].v-=tmp;if(e[i].v)cur[x]=i; 66 e[i^1].v+=tmp;used+=tmp; 67 if(used==f)return f; 68 } 69 if(!used) h[x]=-1; 70 return used; 71 } 72 void dinic() 73 { 74 maxflow=0; 75 while(bfs()) 76 { 77 for (int i=s;i<=t;i++)cur[i]=head[i];maxflow+=dfs(s,inf); 78 } 79 } 80 bool check(int mid) 81 { 82 memset(head,0,sizeof(head));tot=1; 83 memset(out,0,sizeof(out)); 84 memset(in,0,sizeof(in)); 85 sum=0;s=0;t=n+1; 86 for1(i,m) 87 { 88 if(w1[i]<=mid)out[u[i]]++,in[v[i]]++; 89 if(w2[i]<=mid)add(u[i],v[i],1); 90 } 91 for1(i,n)if(abs(in[i]-out[i])&1)return 0; 92 for1(i,n) 93 { 94 int x=in[i]-out[i]; 95 sum+=x>0?x>>1:0; 96 if(x>0)add(i,t,x>>1); 97 if(x<0)add(s,i,(-x)>>1); 98 } 99 dinic();100 return maxflow==sum;101 }102 int main()103 {104 freopen("input.txt","r",stdin);105 freopen("output.txt","w",stdout);106 n=read();m=read();107 int l=inf,r=-inf;108 for1(i,m)109 {110 u[i]=read();v[i]=read();w1[i]=read();w2[i]=read();111 if(w1[i]>w2[i])swap(w1[i],w2[i]),swap(u[i],v[i]);112 l=min(l,w1[i]);r=max(r,w2[i]);113 }114 while(l<=r)115 {116 int mid=(l+r)>>1;117 if(check(mid))r=mid-1;else l=mid+1;118 }119 if(!check(l))printf("NIE\n");else printf("%d\n",l);120 return 0;121 }
2095: [Poi2010]Bridges
Time Limit: 10 Sec Memory Limit: 259 MBSubmit: 243 Solved: 79
[Submit][Status]
Description
YYD为了减肥，他来到了瘦海，这是一个巨大的海，海中有n个小岛，小岛之间有m座桥连接，两个小岛之间不会有两座桥，并且从一个小岛可以到另外任意一个小岛。现在YYD想骑单车从小岛1出发，骑过每一座桥，到达每一个小岛，然后回到小岛1。霸中同学为了让YYD减肥成功，召唤了大风，由于是海上，风变得十分大，经过每一座桥都有不可避免的风阻碍YYD，YYD十分ddt，于是用泡芙贿赂了你，希望你能帮他找出一条承受的最大风力最小的路线。
Input
输入：第一行为两个用空格隔开的整数n（2<=n<=1000），m(1<=m<=2000)，接下来读入m行由空格隔开的4个整数a，b（1<=a,b<=n,a<>b），c，d(1<=c,d<=1000)，表示第i+1行第i座桥连接小岛a和b，从a到b承受的风力为c，从b到a承受的风力为d。
Output
输出：如果无法完成减肥计划，则输出NIE，否则第一行输出承受风力的最大值（要使它最小)
Sample Input
1 2 2 4
2 3 3 4
3 4 4 4
4 1 5 4
Sample Output
HINT
Source
by poi
BZOJ2095: [Poi2010]Bridges