[POI2010]MOS-Bridges

题目描述

洛谷传送门

LOJ 传送门

思路

好恶心好恶心的网络瘤题，属于是知道结论就会做但是会写挂的题，佩服出题人脑洞。

性质：对于一条欧拉回路，每个点的入度 = 出度

首先可以考虑二分答案，二分最小权值 $x$，对于每个 $x$，我们可以建出一张图来，在这张图中，我们把所有不符合条件的边砍掉（变成有向边，记得判断联通）。

考虑先处理有向边：

把所有的点分类，可以分为入度 > 出度 和 入度 < 出度 两类，然后建立源点和汇点。

对于一个入度 > 出度的点，源点向它连一条 （入度 - 出度）/ 2 的边；

对于一个入度 < 出度的点，它向汇点连一条 （出度 - 入度）/ 2 的边。

接下来考虑无向边：

对于无向边 $(u,v)$，我们可以钦定一个方向（假设为 $u \to v$），然后连一条 $v \to u$ 容量为 $1$ 的边即可。

然后注意判断存在 入度-出度 为奇数边则一定无解。

接下来跑网络流。

然后扫描残量网络，如果 入度 > 出度的点未满流，则无解。

然后我们就得到了第一问的答案，根据这个答案建图求欧拉回路即可。

代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e3 + 10;
const int MAXM = 40010;
const int INF = 0x3f3f3f3f;

int N, M, L, R, Ans = 1001;
int U[MAXM], V[MAXM], W1[MAXM], W2[MAXM];

int Fa[MAXN];
int Cnt, ToT;

int Find(int u) {
	return Fa[u] == u ? Fa[u] : Fa[u] = Find(Fa[u]);
}

void Merge(int x, int y) {
	x = Find(x);
	y = Find(y);
	if (x != y) {
		Cnt--;
		Fa[x] = y;
	}
}

bitset<1010> Used;

class MF {
public:
	int Head[MAXN << 1];
	struct _ {
		int To , Next , Value;
	} G[MAXM << 1];
	int Cnt = 1;
	
	void _add(int u , int v , int w) {
		G[++Cnt].To = v;
		G[Cnt].Next = Head[u];
		G[Cnt].Value = w;
		Head[u] = Cnt;
	}
	
	int Depth[MAXN] , Hash[MAXN];
	
	void BFS() {
		memset(Depth , -1 , sizeof Depth);
		memset(Hash , 0 , sizeof Hash);
		Depth[T] = 0;
		Hash[0]++;
		queue<int> q;
		q.push(T);
		
		while(q.size()) {
			int u = q.front();
			q.pop();
			for(int i = Head[u]; i ; i = G[i].Next) {
				int v = G[i].To;
				if(Depth[v] != -1) continue;
				Depth[v] = Depth[u] + 1;
				Hash[Depth[v]]++;
				q.push(v);
			}
		}
		return;
	}
	
	int Max_flow = 0;
	
	int DFS(int u , int flow) {
		if(u == T) {
			Max_flow += flow;
			return flow;
		}
		
		int used = 0;
		for(int i = Head[u]; i; i = G[i].Next) {
			int v = G[i].To;
			if(G[i].Value && Depth[v] == Depth[u] - 1) {
				int Min = DFS(v , min(G[i].Value , flow - used));
				if(Min) {
					G[i].Value -= Min;
					G[i ^ 1].Value += Min;
					used += Min;
				}
				if(used == flow) {
					return used;
				} 
			}
		}
		
		Hash[Depth[u]]--;
		if(Hash[Depth[u]] == 0) Depth[S] = T + 1;
		Depth[u]++;
		Hash[Depth[u]]++;
		return used;
	}

	int S, T;
	void Add(int u , int v , int w) {
		_add(u , v , w);
		_add(v , u , 0);
	}
	void clear() {
		memset(Head, 0, sizeof Head);
		Cnt = 1;
	}
	int ISAP() {
		Max_flow = 0;
		BFS();
		while(Depth[S] < T + 1) DFS(S , INF);
		return Max_flow;
	}
	int GetSize() {
		return Cnt;
	}
} Flow;

int Degree[MAXN], Id[MAXN];

bool Build(int mid) {
	Flow.clear();
	memset(Degree, 0, sizeof Degree);
	Flow.S = N + 1;
	Flow.T = N + 2;
	ToT = 0;
	for (int i = 1; i <= M; i++) {
		if (W1[i] <= mid) {
			Degree[U[i]]--;
			Degree[V[i]]++;
		}
		if (W2[i] <= mid) {
			Id[i] = Flow.GetSize() + 1;
			Flow.Add(V[i], U[i], 1);
		}
		if (W1[i] > mid) return false;
	}
	for (int i = 1; i <= N; i++) {
		if (Degree[i] & 1) {
			return false;
		}
	}
	for (int i = 1; i <= N; i++) {
		if (Degree[i] > 0) {
			ToT += Degree[i] / 2;
			Flow.Add(Flow.S, i, Degree[i] / 2);
		} else {
			Flow.Add(i, Flow.T, -Degree[i] / 2);
		}
	}
	return true;
}

bool Check(int x) {
	bool res = Build(x);
	if (!res) return false;
	return Flow.ISAP() == ToT;
}

stack<int> Stack[MAXN], res;

void Euler(int u) {
	while (!Stack[u].empty()) {
		int i = Stack[u].top();
		Stack[u].pop();
		Euler(U[i] ^ V[i] ^ u);
		res.push(i);
	}
}

bool Vis[MAXN];

void GetAns() {
	Build(Ans);
	Flow.ISAP();
	for (int i = 1, u, v; i <= M; i++) {
		u = U[i];
		v = V[i];
		if (W1[i] <= Ans && W2[i] <= Ans) {
			if (Flow.G[Id[i]].Value) Stack[u].push(i);
			else Stack[v].push(i);
		} else {
			if (W1[i] <= Ans) Stack[u].push(i);
			else if (W2[i] <= Ans) Stack[v].push(i);
		}
	}
	Euler(1);
	while (res.size()) {
		cout << res.top() << " ";
		res.pop();
	}
	return;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin >> N >> M;
	L = 1001, R = 0, Cnt = N;
	
	for (int i = 1; i <= N; i++) Fa[i] = i;
	
	for (int i = 1; i <= M; i++) {
		cin >> U[i] >> V[i] >> W1[i] >> W2[i];
		Used[U[i]] = 1;
		Used[V[i]] = 1;
		if (W1[i] > W2[i]) {
			swap(U[i], V[i]);
			swap(W1[i], W2[i]);
		}
		Merge(U[i], V[i]);
		L = min(W1[i], L);
		R = max(W2[i], R);
	}
	
	for (int i = 1; i <= N; i++) {
		if (!Used[i]) {
			ToT++;
		}
	}

	if (Cnt - ToT != 1 && Cnt != 1) {
		cout << "NIE" << endl;
		return 0;
	}
	while (L <= R) {
		int mid = L + R >> 1;
		if (Check(mid)) {
			R = mid - 1;
			Ans = mid;
		} else {
			L = mid + 1;
		}
	}

	if (Ans == 1001) {
		cout << "NIE" << endl;
		return 0;
	}
	
	cout << Ans << endl;
	GetAns();
	return 0;
}