题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2095
这个题目啊!瞄一眼就知道是二分吧?
接下来就是给你一些有向边&无向边,让你判断是否存在欧拉回路
对于有向边,没有悬念,直接记录对于出度入度的贡献
只与有向边嘛,不妨先随便定一个向,然后考虑使用网络流进行调整
具体细节可以参见:http://blog.csdn.net/wzq_qwq/article/details/48651379
#include<bits/stdc++.h>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
using namespace std;
const int N = 2000+9;
const int M = 10000+9;
const int INF = 1e9;
struct Edge{int u,v,w1,w2;}edge[M];
int n,m,MX,MN=INF,in[N],out[N],cur[M];
int S,T,dis[N],flow[M],head[N],nxt[M],to[M],TT;
queue<int> que;
inline int read(){
char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}
inline void Add_Edge(int u, int v, int f) {
to[++TT] = v; nxt[TT] = head[u]; head[u] = TT; flow[TT] = f;
to[++TT] = u; nxt[TT] = head[v]; head[v] = TT; flow[TT] = 0;
}
inline bool BFS(){
memset(dis,-1,sizeof(dis));
dis[S] = 0; que.push(0);
while (!que.empty()) {
int w = que.front(); que.pop();
for (int i=head[w];i;i=nxt[i]) if (flow[i] && !~dis[to[i]]) {
dis[to[i]] = dis[w] + 1;
que.push(to[i]);
}
}
return ~dis[T];
}
int DFS(int w, int f) {
if (w == T) {
return f;
} else {
int ret = 0;
for (int &i=cur[w],tmp;i && f;i=nxt[i]) {
if (dis[to[i]] == dis[w] + 1) {
tmp = DFS(to[i], min(f, flow[i]));
ret += tmp; f -= tmp;
flow[i] -= tmp; flow[i^1] += tmp;
}
}
return ret;
}
}
inline int Dinic(){
int ret = 0;
while (BFS()) {
memcpy(cur,head,sizeof(head));
ret += DFS(S,INF);
}
return ret;
}
inline bool judge(int lim){
memset(in,0,sizeof(in));
memset(out,0,sizeof(out));
memset(head,0,sizeof(head));
S = 0; T = N - 1; TT = 1;
int tot = 0;
for (int i=1;i<=m;i++) {
if (lim < edge[i].w1) {
continue;
} else if (lim < edge[i].w2) {
in[edge[i].v]++;
out[edge[i].u]++;
} else {
in[edge[i].v]++;
out[edge[i].u]++;
Add_Edge(edge[i].u, edge[i].v, 2);
}
}
for (int i=1;i<=n;i++) {
if (abs(in[i]-out[i]) & 1) {
return false;
} else if (in[i] < out[i]) {
Add_Edge(S,i,out[i]-in[i]);
tot += out[i] - in[i];
} else if (in[i] > out[i]) {
Add_Edge(i,T,in[i]-out[i]);
}
}
return Dinic() == tot;
}
int main(){
n = read(); m = read();
for (int i=1;i<=m;i++) {
edge[i].u = read();
edge[i].v = read();
edge[i].w1 = read();
edge[i].w2 = read();
if (edge[i].w1 > edge[i].w2) {
swap(edge[i].w1, edge[i].w2);
swap(edge[i].u, edge[i].v);
}
MX = max(MX, edge[i].w2);
MN = min(MN, edge[i].w1);
}
int l = MN, r = MX, mid, ret = -1;
while (l <= r) {
mid = l + r >> 1;
if (judge(mid)) ret = mid, r = mid - 1;
else l = mid + 1;
}
if (~ret) printf("%d\n",ret);
else puts("NIE");
return 0;
}