首页 > 代码库 > BZOJ 2095: [Poi2010]Bridges
BZOJ 2095: [Poi2010]Bridges
2095: [Poi2010]Bridges
Time Limit: 10 Sec Memory Limit: 259 MBSubmit: 869 Solved: 299
[Submit][Status][Discuss]
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
4 4
1 2 2 4
2 3 3 4
3 4 4 4
4 1 5 4
1 2 2 4
2 3 3 4
3 4 4 4
4 1 5 4
Sample Output
4
HINT
注意：通过桥为欧拉回路
Source
by poi
分析：
最大值最小的问题...
二分答案，然后就转化成了混合图欧拉回路的存在性问题...可以参考POJ 1637
代码：
#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>//by NeighThorn#define inf 0x3f3f3f3fusing namespace std;const int maxn=1000+5,maxm=10000+5;int n,m,S,T,tot,Min,Max,in[maxn],out[maxn],vis[maxm];int cnt,hd[maxn],fl[maxm],to[maxm],pos[maxn],nxt[maxm];struct M{ int x,y,c,d;}e[maxm];inline void add(int x,int y,int s){ fl[cnt]=s;to[cnt]=y;nxt[cnt]=hd[x];hd[x]=cnt++; fl[cnt]=0;to[cnt]=x;nxt[cnt]=hd[y];hd[y]=cnt++;}inline bool bfs(void){ memset(pos,-1,sizeof(pos)); int head=0,tail=0,q[maxn]; pos[S]=0;q[0]=S; while(head<=tail){ int top=q[head++]; for(int i=hd[top];i!=-1;i=nxt[i]) if(pos[to[i]]==-1&&fl[i]) pos[to[i]]=pos[top]+1,q[++tail]=to[i]; } return pos[T]!=-1;}inline int find(int v,int f){ if(v==T) return f; int res=0,t; for(int i=hd[v];i!=-1&&f>res;i=nxt[i]) if(pos[to[i]]==pos[v]+1&&fl[i]) t=find(to[i],min(fl[i],f-res)),res+=t,fl[i]-=t,fl[i^1]+=t; if(!res) pos[v]=-1; return res;}inline int dinic(void){ int res=0,t; while(bfs()) while(t=find(S,inf)) res+=t; return res;}inline bool check(int val){ cnt=0;tot=0; memset(in,0,sizeof(in)); memset(hd,-1,sizeof(hd)); memset(out,0,sizeof(out)); memset(vis,0,sizeof(vis)); for(int i=1;i<=m;i++){ if(e[i].c<=val) vis[i]+=1; if(e[i].d<=val) vis[i]+=2; } for(int i=1;i<=m;i++){ if(vis[i]==3) in[e[i].y]++,out[e[i].x]++,add(e[i].x,e[i].y,1); else if(vis[i]==1) in[e[i].y]++,out[e[i].x]++; else if(vis[i]==2) in[e[i].x]++,out[e[i].y]++; } for(int i=1;i<=n;i++) if(abs(in[i]-out[i])&1) return false; for(int i=1;i<=n;i++) if(in[i]<out[i]) add(S,i,(out[i]-in[i])/2),tot+=(out[i]-in[i])/2; else if(in[i]>out[i]) add(i,T,(in[i]-out[i])/2); if(dinic()==tot) return true; return false;}signed main(void){#ifndef ONLINE_JUDGE freopen("in.txt","r",stdin);#endif scanf("%d%d",&n,&m);Min=2333;Max=0;S=0,T=n+1; for(int i=1;i<=m;i++) scanf("%d%d%d%d",&e[i].x,&e[i].y,&e[i].c,&e[i].d), Min=min(Min,min(e[i].c,e[i].d)), Max=max(Max,max(e[i].c,e[i].d)); int l=Min,r=Max,ans=-1; while(l<=r){ int mid=(l+r)>>1; if(check(mid)) ans=mid,r=mid-1; else l=mid+1; } if(ans==-1) puts("NIE"); else printf("%d\n",ans); return 0;}
By NeighThorn
BZOJ 2095: [Poi2010]Bridges
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。