Sightseeing tour
网络流 - 最大流
考虑欧拉图,无向边:度数全为偶数,有向边:出度和入度相等
对于有向边来说,已经不可更改;对于无向边来说,可以更改其指向
因此这题最终就是想找一种合理的方案(调整无向边的方向),使得所有点的出度等于入度
首先要判断是否是一个连通图,还要判断,所有点的度数是否为偶数,如果不满足,显然不会是欧拉图
接下来上网络流模型
对于入度大于出度的点,说明有流量要流入这个点,因此建立一个源点到该点的边,流量为 \((in[i] - out[i]) / 2\)
对于出度大于入度的点,说明这个点有流量要流出,因此建立一个该点到汇点的边,流量为 \((out[i] - in[i]) / 2\)
上述流量除以二的原因:对于 入度大于出度的点,每有 \(1\) 个无向边转向,该点的出度 \(+1\),入度 \(-1\),相当于改变了个流量;同理出度大于入度的点也是这样
假定无向边指向一个方向(假定 \(a\) 指向 \(b\)),需要建立一条从 \(b\) 到 \(a\) 的边,流量为 \(1\)
个人认为这个建模,其实就是如果有流量从一个点流出,则有一个以该点发出的有向边转向回来;流量流入一个点,则有一个指向该点的有向边转向;区别有向边和无向边就在于点与点之间的建边
最终答案满足的话,必须是网络流满流,满流才意味着每个点的出度与入度能调整到相等
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
const ll inf = 1e17 + 10;
int head[maxn], nex[maxn], to[maxn], tp = 1, dep[maxn];
int cur[maxn];
ll vol[maxn];
int n, m, s, t;
void add(int l, int r, int w)
{
tp++;
nex[tp] = head[l];
vol[tp] = w;
to[tp] = r;
head[l] = tp;
}
void init()
{
for(int i=0; i<=t; i++) head[i] = 0;
tp = 1;
}
bool bfs()
{
queue<int>q;
for(int i=0; i<=t; i++) dep[i] = -1;
for(int i=0; i<=t; i++) cur[i] = head[i];
q.push(s);
dep[s] = 0;
while(q.size())
{
int now = q.front();
q.pop();
for(int i=head[now]; i; i=nex[i])
{
int u = to[i];
if(dep[u] != -1 || vol[i] <= 0) continue;
dep[u] = dep[now] + 1;
q.push(u);
}
}
return dep[t] != -1;
}
ll dfs(int now, ll flow)
{
if(now == t)
return flow;
ll ans = 0;
for(int i=cur[now]; i && flow; i=nex[i])
{
cur[now] = i;
int u = to[i];
if(vol[i] <= 0 || dep[u] != dep[now] + 1) continue;
ll f = dfs(u, min(flow, vol[i]));
vol[i] -= f;
vol[i ^ 1] += f;
ans += f;
flow -= f;
}
return ans;
}
ll dinic()
{
ll ans = 0;
while(bfs())
ans += dfs(s, inf);
return ans;
}
int top[maxn];
int query(int x)
{
return top[x] == x ? x : top[x] = query(top[x]);
}
int in[maxn], out[maxn];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int tt;
cin >> tt;
while(tt--)
{
init();
cin >> n >> m;
for(int i=0; i<=n; i++) in[i] = out[i] = 0;
int cnt = 0;
for(int i=0; i<=n; i++) top[i] = i;
for(int i=0; i<m; i++)
{
int a, b, c;
cin >> a >> b >> c;
int aa = query(a), bb = query(b);
if(aa != bb)
{
top[aa] = bb;
cnt++;
}
out[a]++;
in[b]++;
if(c == 0)
{
add(b, a, 1);
add(a, b, 0);
}
}
int f = 0;
for(int i=1; i<=n; i++)
{
if((in[i] + out[i]) % 2)
{
f = 1;
break;
}
}
if(f || cnt != n - 1)
{
cout << "impossible\n";
continue;
}
s = n + 1;
t = s + 1;
cnt = 0;
for(int i=1; i<=n; i++)
{
if(in[i] > out[i])
{
cnt += (in[i] - out[i]) / 2;
add(s, i, (in[i] - out[i]) / 2);
add(i, s, 0);
}
else if(in[i] < out[i])
{
add(i, t, (out[i] - in[i]) / 2);
add(t, i, 0);
}
}
ll ans = dinic();
if(ans == cnt) cout << "possible\n";
else cout << "impossible\n";
}
cout << endl;
return 0;
}
标签:int,出度,入度,add,tour,POJ,maxn,Sightseeing,out
From: https://www.cnblogs.com/dgsvygd/p/16758815.html