描述
YYB为了减肥，他来到了瘦海，这是一个巨大的海，海中有n个小岛，小岛之间有m座桥连接，两个小岛之间不会有两座桥，并且从一个小岛可以到另外任意一个小岛。现在YYB想骑单车从小岛1出发，骑过每一座桥，到达每一个小岛，然后回到小岛1。同学为了让YYB减肥成功，召唤了大风，由于是海上，风变得十分大，经过每一座桥都有不可避免的风阻碍YYB，YYB十分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
Analysis
又是一个题目描述不清的提……[嫌弃] 实际意思就是说每个桥必须（也只能）经过1次 这下就明白啦~欧拉回路 面对这种最大值最小的问题，很显然，二分 然后建图，将边权小于等于当前二分答案的边保留 问题就转化为了判定性的： 在我们新建的图上，判断是否存在欧拉回路
常见的判断： 对于有向图 — 每个点的出度 =入度，（且图联通） 对于无向图 — 每个点的度数为偶数，（且图联通） 但是这个地方，我们是对混合图（既有无向边，又有有向边）判断，就不能简单的像上述两种方法判断了 那么我们就利用网络流这个强大的工具来乱搞： 先随便给图中的无向边定方向，算出每个点的出度和入度 如果出度和入度之差为奇数，则这个图肯定不能构成欧拉回路 （因为差为奇数的话，无论你怎么定方向，都不可能找到一种方案使得出度 = 入度） 然后，对于每条定了方向的无向边，我们将其反着建一条流量为1 的边，表示这条边的方向可以翻转 对于每一个点，如果其入度
(
x
)
(x)
(x)大于出度
(
y
)
(y)
(y)，则说明我们需要将
y
−
x
2
\frac{y-x}{2}
2y−x条进入这个点的边的方向改变，才可以达到出入度相等。那么我们就新建一个源点S，从S到这个点连接流量为
y
−
x
2
\frac{y-x}{2}
2y−x的边 同理若入度小于出度，我们就往汇点连 最后跑一遍最大流，若满流，则说明可以找到一种方案使得所有点的出入度相同
Code
#include<bits/stdc++.h>
#define ll long long
#define in read()
#define N 2009
#define M 100009
#define inf (1ll<<31)-1
using namespace std
;
inline int read(){
char ch
;int f
=1,res
=0;
while((ch
=getchar())<'0'||ch
>'9') if(ch
=='-') f
=-1;
while(ch
>='0'&&ch
<='9'){
res
=(res
<<3)+(res
<<1)+ch
-'0';
ch
=getchar();
}
return f
==1?res
:-res
;
}
int n
,m
,S
,T
,mn
,mx
;
int tot
=0,c
[M
],d
[M
];
int u
[M
],v
[M
],du
[N
];
int cur
[N
],lev
[N
];
int nxt
[M
],to
[M
],head
[N
],cap
[M
],ecnt
=1;
inline void add(int x
,int y
,int z
){
nxt
[++ecnt
]=head
[x
];head
[x
]=ecnt
;to
[ecnt
]=y
;cap
[ecnt
]=z
;
nxt
[++ecnt
]=head
[y
];head
[y
]=ecnt
;to
[ecnt
]=x
;cap
[ecnt
]=0;
}
inline void build(int lim
){
tot
=0;
memset(head
,0,sizeof(head
));
memset(du
,0,sizeof(du
));
for(int i
=1;i
<=m
;++i
){
if(c
[i
]<=lim
) du
[u
[i
]]--,du
[v
[i
]]++;
if(d
[i
]<=lim
) add(v
[i
],u
[i
],1);
}
for(int i
=1;i
<=n
;++i
){
if(du
[i
]>0) tot
+=du
[i
]/2,add(S
,i
,du
[i
]/2);
else add(i
,T
,-du
[i
]/2);
}
}
bool bfs(){
for(int i
=S
;i
<=T
;++i
) lev
[i
]=-1,cur
[i
]=head
[i
];
queue
<int> q
;q
.push(S
);lev
[S
]=0;
while(!q
.empty()){
int u
=q
.front();q
.pop();
for(int e
=head
[u
];e
;e
=nxt
[e
]){
int v
=to
[e
];
if(lev
[v
]!=-1||cap
[e
]<=0) continue;
lev
[v
]=lev
[u
]+1;
if(v
==T
) return 1;
q
.push(v
);
}
}
return 0;
}
inline int dinic(int u
,int flow
){
if(u
==T
) return flow
;
int delta
=0,res
=0;
for(int &e
=cur
[u
];e
;e
=nxt
[e
]){
int v
=to
[e
];
if(lev
[v
]>lev
[u
]&&cap
[e
]){
delta
=dinic(v
,min(flow
-res
,cap
[e
]));
if(delta
){
cap
[e
]-=delta
;cap
[e
^1]+=delta
;
res
+=delta
;if(res
==flow
) return flow
;
}
}
}
return res
;
}
inline int maxflow(){
for(int i
=1;i
<=n
;++i
) if(du
[i
]&1) return -1;
int ans
=0;
while(bfs())ans
+=dinic(S
,inf
);
return ans
;
}
int main(){
n
=in
;m
=in
;
S
=0;T
=n
+1;
int i
,j
,k
;
mn
=inf
;mx
=-1;
for(i
=1;i
<=m
;++i
){
u
[i
]=in
;v
[i
]=in
;c
[i
]=in
;d
[i
]=in
;
if(c
[i
]>d
[i
]) swap(c
[i
],d
[i
]),swap(u
[i
],v
[i
]);
mn
=min(mn
,c
[i
]);mx
=max(mx
,d
[i
]);
}
int l
=mn
,r
=mx
,res
=0;
while(l
<=r
){
int mid
=l
+r
>>1;
build(mid
);
if(maxflow()==tot
) res
=mid
,r
=mid
-1;
else l
=mid
+1;
}
if(l
>mx
) printf("NIE");
else printf("%d",res
);
return 0;
}
