问题描述
YYD 为了减肥, 他来到了瘦海, 这是一个巨大的海, 海中有 n 个小岛, 小岛之间有 m 座桥连接, 两个小岛之间不会有两座桥, 并且从一个小岛可以到另外任意一个小岛. 现在 YYD 想骑单车从小岛 1 出发, 骑过每一座桥, 到达每一个小岛, 然后回到小岛 1. 霸中同学为了让 YYD 减肥成功, 召唤了大风, 由于是海上, 风变得十分大, 经过每一座桥都有不可避免的风阻碍 YYD,YYD 十分 ddt, 于是用泡芙贿赂了你, 希望你能帮他找出一条承受的最大风力最小的路线.
输入格式
输入: 第一行为两个用空格隔开的整数 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.
输出格式
输出: 如果无法完成减肥计划, 则输出 NIE, 否则第一行输出承受风力的最大值(要使它最小)
样例输入
- 4 4
- 1 2 2 4
- 2 3 3 4
- 3 4 4 4
- 4 1 5 4
样例输出
4
提示
注意: 通过桥为欧拉回路
解析
题目要求最大承受风力的最小值, 那很明显是二分答案.
二分答案后这个图就会变成一个混合图(也就是既有单向边也有双向边的). 然后只需要判断这个混合图是否为欧拉回路即可.
具体的我们使用网络流模型. 设 d[i]表示一个点入度减出度的值. 对于一条有向边 (u,v), 就直接 d[u]--,d[v]++(即 u 出度加 1,v 入度加 1). 对于一条无向边(u,v), 先假设方向为 u->v. 如果变向, 则会导致 d[u]+=2,d[v]-=2. 最后, 如果是一条欧拉回路, 则每一个 d[i] 都等于 0. 所以, 我们通过改变无向边的方向使任意 d[i]等于 0. 对于 d[i]>0, 从原点向 i 连一条容量为 d[i]/2 的边; 对于 d[i]<0, 向汇点连一条容量为 - d[i]/2 的边. 对于无向边, 若当前方向为 u 到 v, 则从 v 向 u 连一条容量为 1 的边表示变向. 最后如果满流说明是欧拉回路.
对于这道题, 二分一个 mid, 每一条边如果有一个小于等于 mid, 就作为单向边, 两个就作为无向边. 建图跑 Dinic 判断.
代码
- #include <iostream>
- #include <cstdio>
- #include <cstring>
- #include <queue>
- #define N 1002
- #define M 2002
- #define S 0
- #define T n+1
- using namespace std;
- const int inf=1<<30;
- struct edge{
- int u,v,a,b;
- }e[M];
- int head[N],ver[M*10],nxt[M*10],cap[M*10],l;
- int n,m,i,d[N],dis[N];
- int read()
- {
- char c=getchar();
- int w=0;
- while(c<'0'||c>'9') c=getchar();
- while(c<='9'&&c>='0'){
- w=w*10+c-'0';
- c=getchar();
- }
- return w;
- }
- int abs(int x)
- {
- return x<0?-x:x;
- }
- void insert(int x,int y,int z)
- {
- ver[l]=y;
- cap[l]=z;
- nxt[l]=head[x];
- head[x]=l;
- l++;
- ver[l]=x;
- cap[l]=0;
- nxt[l]=head[y];
- head[y]=l;
- l++;
- }
- bool bfs()
- {
- queue<int> q;
- memset(dis,-1,sizeof(dis));
- q.push(S);
- dis[S]=0;
- while(!q.empty()){
- int x=q.front();
- q.pop();
- for(int i=head[x];i!=-1;i=nxt[i]){
- int y=ver[i];
- if(dis[y]<0&&cap[i]>0){
- dis[y]=dis[x]+1;
- q.push(y);
- }
- }
- }
- return (dis[T]>0);
- }
- int Dinic(int x,int flow)
- {
- if(x==T||flow==0) return flow;
- int ans=0;
- for(int i=head[x];i!=-1;i=nxt[i]){
- int y=ver[i];
- if(dis[y]==dis[x]+1&&cap[i]>0){
- int a=Dinic(y,min(flow,cap[i]));
- flow-=a;
- ans+=a;
- cap[i]-=a;
- cap[i^1]+=a;
- }
- if(flow==0) break;
- }
- if(flow) dis[x]=-1;
- return ans;
- }
- bool check(int x)
- {
- memset(head,-1,sizeof(head));
- memset(d,0,sizeof(d));
- l=0;
- int ans=0,sum=0;
- for(int i=1;i<=m;i++){
- if(e[i].a<=x) d[e[i].u]--,d[e[i].v]++;
- if(e[i].b<=x) insert(e[i].v,e[i].u,1);
- }
- for(int i=1;i<=n;i++){
- if(abs(d[i])%2==1) return 0;
- if(d[i]<0) insert(i,T,-d[i]/2);
- else insert(S,i,d[i]/2),sum+=d[i]/2;
- }
- while(bfs()) ans+=Dinic(S,inf);
- return (ans==sum);
- }
- int main()
- {
- int l=inf,r=-inf,mid,ans=-1;
- n=read();m=read();
- for(i=1;i<=m;i++){
- e[i].u=read();e[i].v=read();
- e[i].a=read();e[i].b=read();
- if(e[i].a>e[i].b){
- swap(e[i].u,e[i].v);
- swap(e[i].a,e[i].b);
- }
- l=min(l,e[i].a);
- r=max(r,e[i].b);
- }
- while(l<=r){
- mid=(l+r)/2;
- if(check(mid)){
- ans=mid;
- r=mid-1;
- }
- else l=mid+1;
- }
- if(ans==-1) puts("NIE");
- else printf("%d\n",ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3240810.html