自动搬运

查看原文

来自洛谷，原作者为

	Lucky_Glass 以心为名，名曰爱惜

搬运于2025-08-24 21:49:41，当前版本为作者最后更新于2020-11-26 09:22:20，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

# 解析

最小化最大权，可以想到二分。

二分得到限制“花费不超过 $c$”，我们发现有一些边的某一个方向被禁了，变成了有向边；另一些边两个方向都可以走，是无向边（两个方向都被禁了显然不合法）。

判断二分出的答案是否可行，就是判断这个既有无向边又有有向边的图有没有欧拉回路。

无向图的欧拉回路在某种程度上可以转化为有向图的欧拉回路，即给每条边指定一个方向；只要存在一种指定方向的方案，使得得到的有向图有欧拉回路，就说明原无向图有欧拉回路。

同样这道题，可以判断“是否存在一种给无向边指定方向的方案，使得新图有欧拉回路”。有向图有欧拉回路的充要条件：

• 弱连通：只要保证二分出的值不会使一条边的两个方向都不能通行即可；
• 每个点，入度等于出度等于度数的一半。

由于一个点入度与出度的和一定，只需要考虑出度为其度数的一半。

• 有向边 $u\to v$ 只能固定给 $u$ 提供一个出度；
• 无向边 $(u,v)$ 要么给 $u$ 提供出度要么给 $v$ 提供出度。

于是就可以用网络流来解决，具体来说：

• 原图的边 $i$ 建点 $e_i$，原图的点 $u$ 建点 $p_u$；
• 源点向 $e_i$ 连容量 $1$ 的边，表示一条边只能提供 $1$ 个出度；
• $p_i$ 向汇点连容量为 $\frac{degree(i)}{2}$ 的边，表示该点需要这么多出度；
• 若 $i$ 边有向，则 $e_i$ 向其起始端点 $j$ 对应的 $p_j$ 连容量 $1$ 的边；若无向则向其两端点分别连容量为 $1$ 的边；表示这条边能给哪些点提供出度。

然后跑最大流，每条边都要提供度数——判断最大流是否为 $m$，再看残余网络上哪些 $e_i\to p_j$ 流过了，就可以确定边 $i$ 的指向。最后 DFS 求出有向图欧拉回路的方案即可。

# 源代码

/*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;
}

THE END

Thanks for reading!