即可)。这样只需求一次最大流。
【典型例题】Sightseeing tour(PKU1637,ZJU1992)
本题就是求混合图的欧拉环问题,题目中已经说明图是连通的(Input的最后一句话),故不需判连通。
(本沙茶一开始把DFS中的l0 = aug中的"= aug"写漏了,TLE了N次)
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
#define re(i, n) for (int i=0; i
const int MAXN = 2002, MAXM = 10000, INF = ~0U >> 2;
struct edge {
int a, b, f, next;
edge () {}
edge (int _a, int _b, int _f): a(_a), b(_b), f(_f), next(-1) {}
} ed[MAXM + MAXM];
int n, m, s, t, D[MAXN], hd[MAXN], tl[MAXN], lb[MAXN], vl[MAXN], flow, lmt;
bool res;
int dfs(int i, int aug)
{
if (i == t) {flow += aug; return aug;}
int l0 = aug, l1, j, f0;
for (int p=hd[i]; p != -1; p=ed[p].next) {
j = ed[p].b; f0 = ed[p].f;
if (lb[i] == lb[j] + 1 && f0) {
l1 = dfs(j, l0 <= f0 ? l0 : f0);
l0 -= l1; ed[p].f -= l1; ed[p ^ 1].f += l1;
if (lb[s] == n || !l0) return aug;
}
}
int minlb = n - 1;
for (int p=hd[i]; p != -1; p=ed[p].next) if (ed[p].f) {
j = ed[p].b;
if (lb[j] < minlb) minlb = lb[j];
}
if (--vl[lb[i]]) vl[lb[i] = minlb + 1]++; else lb[s] = n;
return aug - l0;
}
inline void add_edge(int a, int b, int f)
{
ed[m] = edge(a, b, f);
if (hd[a] != -1) tl[a] = ed[tl[a]].next = m++; else hd[a] = tl[a] = m++;
ed[m] = edge(b, a, 0);
if (hd[b] != -1) tl[b] = ed[tl[b]].next = m++; else hd[b] = tl[b] = m++;
}
void solve()
{
int tests;
scanf("%d", &tests);
int n0, m0, a0, b0, f;
re(testno, tests) {
scanf("%d%d", &n0, &m0);
n = n0 + 2; m = 0; s = 0; t = n - 1;
memset(D, 0, n0 << 2); memset(hd, -1, n << 2); memset(tl, -1, n << 2);
re(i, m0) {
scanf("%d%d%d", &a0, &b0, &f);
D[a0 - 1]++; D[b0 - 1]--;
if (!f) add_edge(a0, b0, 1);
}
res = 1; lmt = 0; flow = 0;
re(i, n0) {
if (D[i] % 2) {res = 0; break;}
if (D[i] > 0) {add_edge(s, i + 1, D[i] >> 1); lmt += D[i] >> 1;}
if (D[i] < 0) add_edge(i + 1, t, -D[i] >> 1);
}
if (res) {
memset(lb, 0, n << 2); vl[0] = n; memset(vl + 1, 0, n << 2);
while (lb[s] < n) dfs(s, INF);
if (flow < lmt) res = 0;
}
puts(res ? "possible" : "impossible");
}
}
int main()
{
solve();
return 0;
}