https://loj.ac/problem/6122
来回相当于同时在起点开始不相交
跑一个最大费用最大流
最后输出答案时沿着反向边有容量 dfs 就行了
- #include <iostream> #include <map> #include <cstring> #include <queue> using namespace std;
- map <string,
- int> mapp;
- const int maxn = 110;
- string str[maxn];
- const int inf = 0x3f3f3f3f;
- int head[maxn * 2];
- int tot = 0;
- struct edge {
- int v,
- nex,
- w,
- c;
- }
- e[maxn * maxn * 2];
- void addedge(int u, int v, int w, int c) {
- e[tot] = (edge) {
- v,
- head[u],
- w,
- c,
- };
- head[u] = tot++;
- e[tot] = (edge) {
- u,
- head[v],
- 0,
- -c,
- };
- head[v] = tot++;
- }
- int dis[maxn * 2];
- int vis[maxn * 2];
- int pre[maxn * 2];
- bool spfa(int S, int T) {
- memset(dis, 0x3f, sizeof(dis));
- memset(vis, 0, sizeof(vis));
- queue <int> q;
- q.push(S);
- dis[S] = 0;
- vis[S] = 1;
- while (!q.empty()) {
- int now = q.front();
- vis[now] = 0;
- q.pop();
- for (int i = head[now]; i != -1; i = e[i].nex) {
- int v = e[i].v;
- int w = e[i].w;
- int c = e[i].c;
- if (w> 0 && dis[v]> dis[now] + c) {
- dis[v] = dis[now] + c;
- pre[v] = i;
- if (vis[v] == 0) {
- vis[v] = 1;
- q.push(v);
- }
- }
- }
- }
- if (dis[T] == 0x3f3f3f3f) return false;
- return true;
- }
- int ed(int S, int T, int & flow) {
- int p;
- int sum = 0;
- int maxflow = 0x3f3f3f3f;
- for (int i = T; i != S; i = e[p ^ 1].v) {
- p = pre[i];
- maxflow = min(e[p].w, maxflow);
- }
- flow += maxflow;
- for (int i = T; i != S; i = e[p ^ 1].v) {
- p = pre[i];
- sum += e[p].c * maxflow;
- e[p].w -= maxflow;
- e[p ^ 1].w += maxflow;
- }
- return sum;
- }
- int ans1[maxn];
- int ans2[maxn];
- int dfs(int now, int * p, int deep) {
- p[deep] = now;
- for (int i = head[now]; i != -1; i = e[i].nex) {
- int w = e[i ^ 1].w;
- int v = e[i].v;
- if (w> 0) {
- e[i ^ 1].w -= 1;
- return dfs(e[i].v, p, deep + 1);
- }
- }
- return deep + 1;
- }
- int n,
- v;
- void solve(int S, int T) {
- int flow = 0;
- int ans = 0;
- while (spfa(S, T)) {
- ans += ed(S, T, flow);
- }
- if (flow != 2) {
- cout <<"No Solution!" << endl;
- } else {
- cout << ( - ans - 2) << endl;
- int k1,
- k2;
- k1 = dfs(1, ans1, 0);
- k2 = dfs(1, ans2, 0);
- for (int i = 0; i < k1; i += 2) {
- if (ans1[i] == T) continue;
- cout << str[ans1[i]] << endl;
- }
- for (int i = k2 - 1; i>= 0; i -= 2) {
- if (ans2[i] == T) continue;
- if (ans2[i] == n) continue;
- cout <<str[ans2[i]] << endl;
- }
- }
- }
- int main() {
- memset(head, -1, sizeof(head));
- cin>> n>> v;
- int S = 0,
- T = 2 * n + 1;
- for (int i = 1; i <= n; i++) {
- cin>> str[i];
- mapp[str[i]] = i;
- }
- for (int i = 1; i <= v; i++) {
- string u,
- v;
- cin>> u>> v;
- addedge(mapp[u] + n, mapp[v], inf, 0);
- }
- for (int i = 2; i < n; i++) {
- addedge(i, i + n, 1, -1);
- }
- addedge(1, 1 + n, 2, -1);
- addedge(n, n * 2, 2, -1);
- addedge(S, 1, 2, 0);
- addedge(n * 2, T, 2, 0);
- solve(S, T);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2536916.html