MOS-Bridges解析
Lucky_Glass · · 题解
# 解析
最小化最大权，可以想到二分。
二分得到限制“花费不超过
判断二分出的答案是否可行，就是判断这个既有无向边又有有向边的图有没有欧拉回路。
无向图的欧拉回路在某种程度上可以转化为有向图的欧拉回路，即给每条边指定一个方向；只要存在一种指定方向的方案，使得得到的有向图有欧拉回路，就说明原无向图有欧拉回路。
同样这道题，可以判断“是否存在一种给无向边指定方向的方案，使得新图有欧拉回路”。有向图有欧拉回路的充要条件：
- 弱连通：只要保证二分出的值不会使一条边的两个方向都不能通行即可；
- 每个点，入度等于出度等于度数的一半。
由于一个点入度与出度的和一定，只需要考虑出度为其度数的一半。
- 有向边
u\to v 只能固定给u 提供一个出度； - 无向边
(u,v) 要么给u 提供出度要么给v 提供出度。
于是就可以用网络流来解决，具体来说：
- 原图的边
i 建点e_i ，原图的点u 建点p_u ； - 源点向
e_i 连容量1 的边，表示一条边只能提供1 个出度； -
- 若
i 边有向，则e_i 向其起始端点j 对应的p_j 连容量1 的边；若无向则向其两端点分别连容量为1 的边；表示这条边能给哪些点提供出度。
然后跑最大流，每条边都要提供度数——判断最大流是否为
# 源代码
/*Lucky_Glass*/
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef pair<int,int> pii;
const int N=1e3+10,M=2e3+10,INF=0x3f3f3f3f;
const int NP=N+M,NE=3*M+N;
#define ci const int &
inline int Read(int &r){
int b=1,c=getchar();r=0;
while(c<'0' || '9'<c) b=c=='-'? -1:b,c=getchar();
while('0'<=c && c<='9') r=(r<<1)+(r<<3)+(c^'0'),c=getchar();
return r*=b;
}
struct EDGE{
int u,v,tov,tou;
void Input(){Read(u),Read(v),Read(tov),Read(tou);}
}edg[M];
struct FLOWGRAPH{
int head[NP],to[NE<<1],nxt[NE<<1],cap[NE<<1],ncnt;
void Init(ci n){
for(int i=0;i<=n;i++) head[i]=0;
ncnt=1;
}
void AddEdge(ci u,ci v,ci ca){
int p=++ncnt,q=++ncnt;
to[p]=v,nxt[p]=head[u],head[u]=p,cap[p]=ca;
to[q]=u,nxt[q]=head[v],head[v]=q,cap[q]=0;
}
inline int operator [](ci u){return head[u];}
}Fl;
struct GRAPH{
int head[N],to[M],nxt[M],id[M],ncnt;
void AddEdge(ci u,ci v,ci i){
int p=++ncnt;
to[p]=v,nxt[p]=head[u],head[u]=p;
id[p]=i;
}
inline int& operator [](ci u){return head[u];}
}Gr;
struct QUEUE{
int ary[NP],ql,qr;
inline void clear(){ql=1,qr=0;}
inline void push(ci x){ary[++qr]=x;}
inline void pop(){ql++;}
inline bool empty(){return ql>qr;}
inline int front(){return ary[ql];}
}que;
int n,m,S,T,nans,deg[N],head[NP],dis[NP],tp[N],ans[M];
int Aug(ci u,ci in){
if(u==T) return in;
int out=0;
for(int &it=head[u];it;it=Fl.nxt[it]){
int v=Fl.to[it];
if(Fl.cap[it]<=0 || dis[v]!=dis[u]+1) continue;
int tov=Aug(v,min(in-out,Fl.cap[it]));
Fl.cap[it]-=tov,Fl.cap[it^1]+=tov;
out+=tov;
if(out==in) break;
}
return out;
}
bool BFS(){
for(int i=1;i<=T;i++) head[i]=Fl[i],dis[i]=-1;
que.clear();
dis[S]=0,que.push(S);
while(!que.empty()){
int u=que.front();que.pop();
for(int it=head[u];it;it=Fl.nxt[it]){
int v=Fl.to[it];
if((~dis[v]) || Fl.cap[it]<=0) continue;
dis[v]=dis[u]+1;
if(v==T) return true;
que.push(v);
}
}
return false;
}
bool Check(ci mid){
Fl.Init(T);
int ept=0;
for(int i=1;i<=n;i++)
Fl.AddEdge(i,T,deg[i]/2),ept+=deg[i]/2;
for(int i=1;i<=m;i++){
Fl.AddEdge(S,n+i,1);
if(edg[i].tov<=mid) Fl.AddEdge(n+i,edg[i].v,1);
if(edg[i].tou<=mid) Fl.AddEdge(n+i,edg[i].u,1);
}
int out=0;
while(BFS())
out+=Aug(S,INF);
return out==ept;
}
void DFS(ci u,ci las){
while(Gr[u]){
int it=Gr[u];Gr[u]=Gr.nxt[it];
int v=Gr.to[it];
DFS(v,Gr.id[it]);
}
if(las) ans[++nans]=las;
}
int main(){
// freopen("input.in","r",stdin);
int lef=0,rig=0;
Read(n),Read(m),S=n+m+1,T=S+1;
for(int i=1;i<=m;i++){
edg[i].Input();
rig=max(rig,max(edg[i].tou,edg[i].tov));
lef=max(lef,min(edg[i].tou,edg[i].tov));
deg[edg[i].u]++,deg[edg[i].v]++;
}
for(int i=1;i<=n;i++)
if(deg[i]&1){
printf("NIE\n");
return 0;
}
while(lef+1<rig){
int mid=(lef+rig)>>1;
if(Check(mid)) rig=mid;
else lef=mid;
}
int ans;
if(!Check(lef)) ans=rig,Check(rig);
else ans=lef;
printf("%d\n",ans);
for(int i=1;i<=m;i++)
for(int it=Fl[i+n];it;it=Fl.nxt[it]){
if((it&1) || Fl.cap[it]>0) continue;
int v=Fl.to[it];
if(v==edg[i].v) Gr.AddEdge(edg[i].u,edg[i].v,i);
else Gr.AddEdge(edg[i].v,edg[i].u,i);
}
DFS(1,0);
for(int i=m;i>=1;i--) printf("%d%c",::ans[i],i==1? '\n':' ');
return 0;
}