OI - 桥Bridges(LOJ) | Lucky_Glass's Blog

以心为名，名为爱惜

0%

OI - 桥Bridges(LOJ)

发表于 更新于 分类于 Valine：

洛谷的翻译怎么回事（

# 题面

> Linked 洛谷 P3511

> Linked LOJ 2460

点击展开/折叠 题面

$n$ 个点 $m$ 条边，边 $(u,v)$ 有两个代价：从 $u$ 到 $v$ 花费为 $a$，从 $v$ 到 $u$ 花费为 $b$。

从 $1$ 点出发，经过每条边恰好一次，最小化经过的边的最大花费。

$n\le1000,m\le2000$

# 解析

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

二分得到限制“花费不超过 $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 求出有向图欧拉回路的方案即可。

# 源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
/*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!