Euler loop / Bridge

Title Link: YBT2022 winter vacation Day3 B / LOJ 2460

General idea of the topic

Give you a picture, the side is two-way, and the cost of walking on both sides is different.
You should choose some edges to walk, and then form an Euler loop, and the maximum cost of the selected edge is the least.
To output this cost and the selected edge.

thinking

First of all, the maximum cost is the minimum, which is directly divided into two points.

Then there is judgment. We can divide the edges into two categories:
There can only be one direction and both directions. (if you can't walk on both sides, you can't, because your Euler circuit has to go through all sides)
If there is only one direction, it is directly determined, and if there are two directions, it is uncertain.

First, if we judge whether an Euler loop is formed, that is, the in and out degrees of each point should be the same.
If you consider using network flow to choose two directions, you will find that it will have the problem of half flow.

So there is a small way: you choose a direction at first, and then if you choose back, it is a point in degree reduction 2 2 2. Output plus 2 2 2. The other point is reversed.
So every time either 0 0 0 or 2 2 2. We can collectively reduce the traffic / 2 /2 /2 become 0 , 1 0,1 0,1, so there will be no half flow.
Specifically, you choose the side first, and then there is one for each point Δ \Delta Δ Is the difference between in and out, if Δ > 0 \Delta >0 Δ> 0 is connected to it from the source point, and the flow is Δ 2 \dfrac{\Delta}{2} two Δ , if < 0 <0 < 0 is connected to the sink, and the flow is − Δ 2 \dfrac{-\Delta}{2} 2−Δ​.
(if) Δ \Delta Δ It's definitely not OK if it's an odd number, but it's not difficult to see that it must be an even number)
Then as for the side that can go in both directions ( x , y ) (x,y) (x,y), I started with x → y x\rightarrow y x → y, then from y y y to x x x connected to one side, the flow is 1 1 1.

Then judge whether the edges connected from the source point to the sink point are full.

Then pay attention to judge NIE, that is, if the unconnected graph is NIE, the original undirected graph has no Euler circuit and is NIE.

code

#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#define INF 0x3f3f3f3f3f3f3f3f

using namespace std;

struct node {
	int x, y, v1, v2;
}a[2001];
int n, m, L, R, ans;
int ru[2001], chu[2001];
int fa[2001], S, T, tot;
int dy[2001];
vector <int> b[2001], goo[2001], pl[2001], answ;

struct water {
	int x, to, nxt, op, fr;
}e[2000001];
int le[2001], KK, lee[2001];

int find(int now) {
	if (fa[now] == now) return now;
	return fa[now] = find(fa[now]);
}

void merge(int x, int y) {
	int X = find(x), Y = find(y);
	if (X == Y) return ;
	fa[X] = Y;
}

void Add(int x, int y, int z, int k) {
	e[++KK] = (water){z, y, le[x], KK + 1, k}; le[x] = KK;
	e[++KK] = (water){0, x, le[y], KK - 1, k}; le[y] = KK;
}

queue <int> q;
int dis[2001];

bool bfs() {
	while (!q.empty()) q.pop();
	memset(dis, 0, sizeof(dis));
	for (int i = 1; i <= tot; i++) lee[i] = le[i];
	dis[S] = 1; q.push(S);
	while (!q.empty()) {
		int now = q.front(); q.pop();
		
		for (int i = le[now]; i; i = e[i].nxt)
			if (e[i].x && !dis[e[i].to]) {
				dis[e[i].to] = dis[now] + 1;
				if (e[i].to == T) return 1;
				q.push(e[i].to);
			}
	}
	
	return 0;
}

int dfs(int now, int sum) {
	if (now == T) return sum;
	
	int go = 0;
	for (int &i = lee[now]; i; i = e[i].nxt)
		if (e[i].x && dis[e[i].to] == dis[now] + 1) {
			int this_go = dfs(e[i].to, min(e[i].x, sum - go));
			if (this_go) {
				e[i].x -= this_go; e[e[i].op].x += this_go;
				go += this_go; if (go == sum) return go;
			}
		}
	
	if (go != sum) dis[now] = -1;
	return go;
}

int Dinic() {
	int re = 0;
	while (bfs())
		re += dfs(S, INF);
	return re;
}

bool check(int k) {
	KK = 0; memset(le, 0, sizeof(le));
	tot = n; S = ++tot; T = ++tot;
	
	memset(ru, 0, sizeof(ru)); memset(chu, 0, sizeof(chu));
	for (int i = 1; i <= m; i++) {
		if (a[i].v1 <= k && a[i].v2 <= k) {
			chu[a[i].x]++; ru[a[i].y]++;
			Add(a[i].y, a[i].x, 1, i);
		}
		else if (a[i].v1 <= k) {
			chu[a[i].x]++; ru[a[i].y]++;
		}
		else {
			chu[a[i].y]++; ru[a[i].x]++;
		}
	}
	
	int sum = 0;
	for (int i = 1; i <= n; i++) {
		int derta = ru[i] - chu[i];
		if (derta > 0) Add(S, i, derta / 2, 0), sum += derta / 2;
			else if (derta < 0) Add(i, T, -derta / 2, 0);
	}
	
	int nowsum = Dinic();
	return nowsum == sum;
}

int num;
bool in[2001];

void Runway(int now) {
	for (int i = 0; i < b[now].size(); i++) {
		if (goo[now][i]) continue;
			else {
				goo[now][i] = 1;
				Runway(b[now][i]);
				answ.push_back(pl[now][i]);
			}
	}
}

int main() {
//	freopen("euler.in", "r", stdin);
//	freopen("euler.out", "w", stdout);
	
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++) fa[i] = i;
	
	for (int i = 1; i <= m; i++) {
		scanf("%d %d %d %d", &a[i].x, &a[i].y, &a[i].v1, &a[i].v2);
		L = max(L, min(a[i].v1, a[i].v2));
		R = max(R, max(a[i].v1, a[i].v2));
		ru[a[i].x]++; ru[a[i].y]++;
		merge(a[i].x, a[i].y);
	}
	
	for (int i = 1; i <= n; i++)
		if (find(i) != find(1)) {
			printf("NIE"); return 0;
		}
	for (int i = 1; i <= n; i++)
		if (ru[i] & 1) {
			printf("NIE"); return 0;
		}
		else ru[i] = 0;
	
	while (L <= R) {
		int mid = (L + R) >> 1;
		if (check(mid)) ans = mid, R = mid - 1;
			else L = mid + 1;
	}
	printf("%d\n", ans);
	
	check(ans);
	for (int i = 1; i <= m; i++) {
		if (a[i].v1 <= ans && a[i].v2 <= ans) {
		}
		else if (a[i].v1 <= ans) {
			b[a[i].x].push_back(a[i].y); goo[a[i].x].push_back(0);
			pl[a[i].x].push_back(i);
		}
		else {
			b[a[i].y].push_back(a[i].x); goo[a[i].y].push_back(0);
			pl[a[i].y].push_back(i);
		}
	}
	for (int x = 1; x <= n; x++) {
		for (int i = le[x]; i; i = e[i].nxt)
			if (e[i].fr && !e[i].x) {
				int y = e[i].to;
				b[x].push_back(y); goo[x].push_back(0);
				pl[x].push_back(e[i].fr);
			}
	}
	Runway(1);
	
	for (int i = answ.size() - 1; i >= 0; i--)
		printf("%d ", answ[i]);
	
	return 0;
}