正文
UVa 10735 - Euler Circuit（最大流 + 欧拉回路）
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
链接：
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1676
题意：
给出一个V个点和E条边（1≤V≤100，1≤E≤500）的混合图（即有的边是无向边，有的边是有向边），
试求出它的一条欧拉回路，如果没有，输出无解信息。输入保证在忽略边的方向之后图是连通的。
分析：
很多混合图问题（例如，混合图的最短路）都可以转化为有向图问题，方法是把无向边拆成两条方向相反的有向边。
可惜本题不能使用这种方法，因为本题中的无向边只能经过一次，
而拆成两条有向边之后变成了“沿着两个相反方向各经过一次”。所以本题不能拆边，而只能给边定向。
假设输入的原图为G。首先把它的无向边任意定向，然后把定向后的有向边单独组成另外一个图G'。
具体来说，初始时G'为空，对于G中的每条无向边u-v，把它改成有向边u->v，然后在G'中连一条边u->v
（注意这个定向是任意的。如果定向为v->u，则在G'中连一条边v->u）。
接下来检查每个点i在G中的入度和出度。如果所有点的入度和出度相等，则现在的G已经存在欧拉回路。
假设一个点的入度为2，出度为4，则可以想办法把一条出边变成入边（前提是那条出边原来是无向边），
这样入度和出度就都等于3了；一般地，如果一个点的入度为in(i)，出度为out(i)，
则只需把出度增加(in(i)-out(i))/2即可（因为总度数不变，此时入度一定会和出度相等）。
如果in(i)和out(i)的奇偶性不同，则问题无解。
如果把G'中的一条边u->v反向成v->u，则u的出度减1，v的出度加1，
就像是把一个叫“出度”的物品从结点u“运输”到了结点v。是不是很像网络流？
也就是说，满足out(i)>in(i)的每个点能“提供”一些“出度”，而out(i)<in(i)的点则“需要”一些“出度”。
如果能算出一个网络流，把这些“出度”运输到需要它们的地方，问题就得到了解决（有流量的边对应"把边反向"操作）。
具体实现见代码。
代码：
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std; /// 结点下标从0开始，注意maxn
struct Dinic {
static const int maxn = 1e3 + ;
static const int INF = 0x3f3f3f3f;
struct Edge {
int from, to, cap, flow;
}; int n, m, s, t; // 结点数，边数（包括反向弧），源点编号和汇点编号
vector<Edge> edges; // 边表。edges[e]和edges[e^1]互为反向弧
vector<int> G[maxn]; // 邻接表，G[i][j]表示结点i的第j条边在e数组中的序号
bool vis[maxn]; // BFS使用
int d[maxn]; // 从起点到i的距离
int cur[maxn]; // 当前弧下标 void init(int n) {
this->n = n;
edges.clear();
for(int i = ; i < n; i++) G[i].clear();
}
void AddEdge(int from, int to, int cap) {
edges.push_back((Edge){from, to, cap, });
edges.push_back((Edge){to, from, , });
m = edges.size();
G[from].push_back(m-);
G[to].push_back(m-);
}
bool BFS() {
memset(vis, , sizeof(vis));
queue<int> Q;
Q.push(s);
vis[s] = ;
d[s] = ;
while(!Q.empty()) {
int x = Q.front(); Q.pop();
for(int i = ; i < G[x].size(); i++) {
Edge& e = edges[G[x][i]];
if(!vis[e.to] && e.cap > e.flow) { // 只考虑残量网络中的弧
vis[e.to] = ;
d[e.to] = d[x] + ;
Q.push(e.to);
}
}
}
return vis[t];
}
int DFS(int x, int a) {
if(x == t || a == ) return a;
int flow = , f;
for(int& i = cur[x]; i < G[x].size(); i++) { // 从上次考虑的弧
Edge& e = edges[G[x][i]];
if(d[x]+ == d[e.to] && (f=DFS(e.to, min(a, e.cap-e.flow))) > ) {
e.flow += f;
edges[G[x][i]^].flow -= f;
flow += f;
a -= f;
if(a == ) break;
}
}
return flow;
}
int Maxflow(int s, int t) {
this->s = s; this->t = t;
int flow = ;
while(BFS()) {
memset(cur, , sizeof(cur));
flow += DFS(s, INF);
}
return flow;
}
vector<int> Mincut() { // 在Maxflow之后调用
vector<int> ans;
for(int i = ; i < edges.size(); i++) {
Edge& e = edges[i];
if(vis[e.from] && !vis[e.to] && e.cap > ) ans.push_back(i);
}
return ans;
}
} dc; const int UP = + ;
int n, m, f[UP], b[UP], directed[UP], out[UP], id[UP];
vector<int> ans, edge[UP], vis[UP]; void euler(int v) {
for(int i = ; i < edge[v].size(); i++) {
if(vis[v][i]) continue;
vis[v][i] = true;
euler(edge[v][i]);
ans.push_back(edge[v][i]+);
}
} void output_ans() {
for(int i = ; i < n; i++) { edge[i].clear(); vis[i].clear(); }
for(int i = ; i < m; i++) {
bool rev = false;
if(!directed[i] && dc.edges[id[i]].flow > ) rev = true;
if(rev) { edge[b[i]].push_back(f[i]); vis[b[i]].push_back(false); }
else { edge[f[i]].push_back(b[i]); vis[f[i]].push_back(false); }
}
ans.clear();
euler();
printf("");
for(int i = ans.size() - ; i >= ; i--) printf(" %d", ans[i]);
printf("\n");
} int main() {
int T;
char s[];
scanf("%d", &T);
while(T--) {
scanf("%d%d", &n, &m);
dc.init(n+);
memset(out, , sizeof(out));
for(int i = ; i < m; i++) {
scanf("%d%d%s", &f[i], &b[i], s);
directed[i] = (s[] == 'D');
f[i]--; b[i]--;
out[f[i]]++; out[b[i]]--;
if(!directed[i]) {
id[i] = dc.edges.size();
dc.AddEdge(f[i], b[i], );
}
} bool ok = true;
for(int i = ; i < n; i++) if(out[i] % != ) { ok = false; break; }
if(ok) {
int start = n, finish = n+, sum = ;
for(int i = ; i < n; i++) {
if(out[i] > ) { dc.AddEdge(start, i, out[i]/); sum += out[i]/; }
else if(out[i] < ) dc.AddEdge(i, finish, -out[i]/);
}
if(sum != dc.Maxflow(start, finish)) ok = false;
}
if(ok) output_ans();
else printf("No euler circuit exist\n");
if(T) printf("\n");
}
return ;
}
