```cpp
/*[POI2010]MOS-Bridges*/
#include<bits/stdc++.h>
using namespace std;
int read(){
char c = getchar();
int x = 0;
while(c < '0' || c > '9') c = getchar();
while(c >= '0' && c <= '9') x = x * 10 + c - 48,c = getchar();
return x;
}
const int N = 2e5 + 10;
struct Edge{
int nxt,point,flow;
}edge[N<<1];
int head[N],tot = 1;
#define ll long long
#define inf 1e9
void add_edge(int u,int v,int flow){
edge[++tot].nxt = head[u];edge[tot].point = v;edge[tot].flow = flow;head[u] = tot;
edge[++tot].nxt = head[v];edge[tot].point = u;edge[tot].flow = 0; head[v] = tot;
}
void add(int u,int v,int flow){
edge[++tot].nxt = head[u];
edge[tot].point = v;
edge[tot].flow = flow;
head[u] = tot;
}
int ss,tt,S,T,w[N];
void Add_edge(int u,int v,int l,int r){
w[u] -= l;w[v] += l;
add_edge(u,v,r-l);
}
int _a[N],_b[N],_l[N],_p[N],n,m;
int dep[N],q[N],cur[N];
bool bfs(){
for(int i = S; i <= T; ++i) dep[i] = 0,cur[i] = head[i];
int l = 1,r = 0;
q[++r] = S;dep[S] = 1;
while(l <= r){
int x = q[l++];
for(int i = head[x]; i ; i = edge[i].nxt){
int y = edge[i].point;
if(edge[i].flow && !dep[y]){
dep[y] = dep[x] + 1;
q[++r] = y;
}
}
}
return dep[T] != 0;
}
int dinic(int x,int flow){
if(x == T || !flow) return flow;
int rest = flow,k = 0;
for(int i = cur[x]; i ; i = edge[i].nxt){
int y = edge[i].point;
if(rest == 0) return flow;
cur[x] = i;
if(edge[i].flow && dep[y] == dep[x] + 1){
k = dinic(y,min(edge[i].flow,rest));
if(!k) dep[y] = -1;
edge[i].flow -= k;
edge[i^1].flow += k;
rest -= k;
}
}
return flow - rest;
}
bool solve(int mid){
memset(head,0,sizeof(head));
tot = 1;memset(w,0,sizeof(w));
ss = n + 2 * m + 1,tt = n + 2 * m + 2;
S = 0,T = tt + 1;
for(int i = 1; i <= m; ++i){
Add_edge(n+i,n+m+i,1,1);
}
Add_edge(ss,1,1,1);Add_edge(1,tt,1,1);
for(int i = 1; i <= m; ++i){
Add_edge(_a[i],n+i,0,1);
Add_edge(_b[i],n+i,0,1);
if(_l[i] <= mid){
Add_edge(n+m+i,_b[i],0,1);
}
if(_p[i] <= mid){
Add_edge(n+m+i,_a[i],0,1);
}
}
ll mxflow = 0;ll sum = 0;
Add_edge(tt,ss,0,1e7);
for(int i = 1; i <= tt; ++i){
if(w[i] > 0) add_edge(S,i,w[i]),sum += w[i];
else add_edge(i,T,-w[i]);
}
while(bfs()){
mxflow += dinic(S,inf);
}
return (mxflow == sum);
}
int deg[N],st[N],top;
bool vis[N];
void dfs(int u){
for(int &i = head[u]; i ; i = edge[i].nxt){
int v = edge[i].point;
int w = edge[i].flow;
if(vis[i]) continue;
vis[i] = vis[i^1] = 1;
dfs(v);
st[++top] = w;
}
}
int main(){
n = read(),m = read();
int l = 0,r = 0;
for(int i = 1; i <= m; ++i){
_a[i] = read(),_b[i] = read(),_l[i] = read(),_p[i] = read();
l = max(l,min(_l[i],_p[i]));
r = max(r,max(_l[i],_p[i]));
deg[_a[i]] ^= 1,deg[_b[i]] ^= 1;
}
for(int i = 1; i <= n; ++i){
if(deg[i]){
puts("NIE");
return 0;
}
}
int ans = 0;
while(l <= r){
int mid = (l + r) >> 1;
if(solve(mid)){
ans = mid;
r = mid - 1;
}
else l = mid + 1;
}
cout<<ans<<endl;
memset(head,0,sizeof(head));
tot = 1;
for(int i = 1; i <= m; ++i){
if(_l[i] <= ans && _p[i] <= ans){
add(_a[i],_b[i],i);
add(_b[i],_a[i],i);
}
else if(_l[i] <= ans){
add(_a[i],_b[i],i);
add(_b[i],_a[i],i);vis[tot] = 1;
}
else{
add(_a[i],_b[i],i);vis[tot] = 1;
add(_b[i],_a[i],i);
}
}
dfs(1);
while(top){
printf("%d ",st[top]);
top--;
}
return 0;
}
```
by y_dove @ 2021-02-22 23:56:51
是假的,此贴终结
by y_dove @ 2021-02-24 16:40:56
草 我也是这个思路 写了 7k 之后调不出来了 /hanx
by Refined_heart @ 2021-12-28 14:05:36