看到最大的最小，首先套一个二分上去就行
二分一个答案 $x$ 之后，只连那些权值 $\le x$ 的边，这个时候的图是一张混合图，即无向边和有向边都有的图。
对于有向图或者无向图的欧拉回路很好判断，混合图的怎么搞呢？
实际上这是一个很经典的模型：首先把无向边任意定向，然后看每个点的入度和出度。因为改变一次无向边的方向可以让其中一个端点的入度 +1，出度 -1，另一个端点的入度 -1，出度 +1。回想欧拉回路存在的充要条件：所有点的出度等于入度，即：入度 - 出度 = 0。这就是网络流中的平衡条件，设立源点 S 汇点 T，S 向入度大于出度的点连容量为差值除以 2，出度大于入度的点连向 T，容量也是差值除以 2。这个图满流的时候说明欧拉回路就存在了。
然后找欧拉回路：直接 dfs 找就可以，考虑到数据对于随机的图不是很好卡，直接随机一下加边顺序即可（
这个题还有点坑：记得 check 的时候判连通性！！！
#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define fillarray(array, value, begin, end) fill((array) + (begin), (array) + (end) + 1, value)
#define fillvector(v, value) fill((v).begin(), (v).end(), value)
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
#define vecfirst (*vec.begin())
#define veclast (*vec.rbegin())
#define vecall(v) (v).begin(), (v).end()
#define vecupsort(v) (sort((v).begin(), (v).end()))
#define vecdownsort(v, type) (sort(vecall(v), greater<type>()))
#define veccmpsort(v, cmp) (sort(vecall(v), cmp))
using namespace std;
const int N = 1050;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
clock_t TIME__START, TIME__END;
void program_end()
{
#ifdef ONLINE
printf("\n\nTime used:
system("pause");
#endif
}
const int MAXN = 1050, MAXM = 20050;
struct dinic
{
struct Edge
{
int to, nxt, flow, id, positive, cap;
} e[MAXM];
int head[MAXN], ecnt = -1, dis[MAXN], cur[MAXN];
void add_edge(int u, int v, int f, int id)
{
e[++ecnt] = {v, head[u], f, id, 1, f};
head[u] = ecnt;
e[++ecnt] = {u, head[v], 0, id, 0, f};
head[v] = ecnt;
}
int n, m, s, t;
bool bfs()
{
memset(dis, 0, sizeof(dis));
queue<int> q;
dis[s] = 1;
q.push(s);
while (!q.empty())
{
int u = q.front();
q.pop();
for (int i = head[u]; ~i; i = e[i].nxt)
{
int v = e[i].to;
if (!dis[v] && e[i].flow > 0)
{
dis[v] = dis[u] + 1;
q.push(v);
}
}
}
return dis[t];
}
int dfs(int u, int flow)
{
if (u == t)
return flow;
int nowflow = 0;
for (int &i = cur[u]; ~i; i = e[i].nxt)
{
int v = e[i].to;
if (dis[v] == dis[u] + 1 && e[i].flow > 0)
{
int tmp = dfs(v, min(flow, e[i].flow));
e[i].flow -= tmp;
e[i ^ 1].flow += tmp;
flow -= tmp;
nowflow += tmp;
if (!flow)
break;
}
}
return nowflow;
}
int solve(int n, int s, int t)
{
this->s = s, this->t = t, this->n = n;
int ans = 0;
while (bfs())
{
memcpy(cur, head, (n + 5) * sizeof(int));
ans += dfs(s, inf);
}
return ans;
}
void init()
{
ecnt = -1;
memset(head, -1, sizeof(head));
memset(e, 0, sizeof(e));
}
} G;
int n, m, ans = -1, S, T;
struct edges
{
int u, v, c1, c2;
int id;
};
vector<edges> vece;
vector<pii> g[N];
int in[N], out[N];
int f[N], vis[N];
int Find(int x) { return x == f[x] ? x : f[x] = Find(f[x]); }
void Union(int x, int y)
{
int fx = Find(x), fy = Find(y);
if (fy != fx)
f[fy] = fx;
}
bool check(int x)
{
G.init();
memarray(in, 0), memarray(out, 0), memarray(vis, 0);
for (int i = 1; i <= n; ++i)
f[i] = i;
for (auto e : vece)
{
if (e.c1 <= x && e.c2 <= x)
{
G.add_edge(e.v, e.u, 1, e.id);
in[e.v]++, out[e.u]++;
Union(e.u, e.v);
}
else if (e.c1 <= x)
in[e.v]++, out[e.u]++, Union(e.u, e.v);
else if (e.c2 <= x)
in[e.u]++, out[e.v]++, Union(e.u, e.v);
}
int tot = 0;
for (int i = 1; i <= n; ++i)
{
int F = Find(i);
if (!vis[F])
vis[F] = 1, tot++;
}
if (tot > 1)
return 0;
int iniflow = 0;
for (int i = 1; i <= n; ++i)
{
if (abs(in[i] - out[i])
return 0;
if (in[i] > out[i])
G.add_edge(S, i, (in[i] - out[i]) / 2, -1), iniflow += (in[i] - out[i]) / 2;
else if (in[i] < out[i])
G.add_edge(i, T, (out[i] - in[i]) / 2, -1);
}
int maxflow = G.solve(T, S, T);
if (maxflow != iniflow)
return 0;
return 1;
}
bool isadd[3050];
bool vise[N];
vector<int> vecans;
void dfsans(int u)
{
for (auto [v, id] : g[u])
{
if (vise[id])
continue;
vise[id] = 1;
dfsans(v);
vecans.push_back(id);
}
}
void workans()
{
check(ans);
memarray(vis, 0);
int rk = 0;
for (auto i : vece)
{
if (max(i.c1, i.c2) <= ans)
{
if (G.e[rk].flow < 1)
g[i.v].push_back({i.u, i.id});
else
g[i.u].push_back({i.v, i.id});
rk += 2;
continue;
}
if (i.c1 <= ans)
g[i.u].push_back({i.v, i.id});
else if (i.c2 <= ans)
g[i.v].push_back({i.u, i.id});
}
for (int i = 1; i <= n; ++i)
random_shuffle(g[i].begin(), g[i].end());
dfsans(1);
reverse(vecall(vecans));
for (auto i : vecans)
printf(
}
inline void solve()
{
scanf(
S = n + 2, T = S + 1;
for (int i = 1; i <= m; ++i)
{
int a, b, l, p;
scanf(
vece.push_back((edges){a, b, l, p, i});
}
int l = 0, r = 1000;
while (l <= r)
{
int mid = (l + r) >> 1;
if (check(mid))
r = mid - 1, ans = mid;
else
l = mid + 1;
}
if (ans == -1)
return puts("NIE"), void();
printf(
workans();
}
int main()
{
TIME__START = clock();
random_device rd;
srand(rd());
int Test = 1;
// scanf(
while (Test--)
{
solve();
// if (Test)
// putchar('\n');
}
TIME__END = clock();
program_end();
return 0;
}
/*
5 7
1 2 1 1
1 3 1 1
2 3 1 1
2 4 10 10
2 5 10 10
3 4 10 10
3 5 10 10
8 14
1 7 2 1
1 8 1 2
2 3 2 1
2 4 1 2
8 5 1 2
8 4 2 1
6 8 2 1
7 2 1 2
4 6 2 1
4 7 1 2
6 3 1 2
7 5 2 1
5 2 2 1
5 6 1 2
*/
Comments NOTHING