Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## Re:貌似不是，最大流可以有相同的点，而本题是路径除了起点和终点不能有相同的点

Posted by ikeay at 2014-10-03 16:37:45 on Problem 3713
In Reply To:貌似不是，最大流可以有相同的点，而本题是路径除了起点和终点不能有相同的点 Posted by:zxxb at 2008-12-30 09:36:00
```We can split every node p into twonodes: p_in and p_out, then we can constructed a directed bipartite graph.

Source Code
Problem: 3713		User: ikeay
Memory: 908K		Time: 3891MS
Language: G++		Result: Accepted

Source Code

#include <assert.h>
#include <ctype.h>
#include <float.h>
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/types.h>

#include <algorithm>
#include <complex>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
using namespace std;

#define SZ(a) (int)(a).size()
#define FOR(i,a,b) for (int i=(a); i<=(b); ++i)
#define REP(i,n) for (int i=0; i<(n); ++i)
#define ALL(c) c.begin(), c.end()
#define CLR(c,n) memset(c, n, sizeof(c))
#define CONTAIN(it, c) (c.find(it) != c.end())
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef long long LL;
template <class T> void checkmin(T &a, T b) { if (b<a) a=b; }
template <class T> void checkmax(T &a, T b) { if (b>a) a=b; }

const int MAXN=512, MAXM=40<<10;
int n, e, head[MAXN], nextid[MAXM], dest[MAXM], match[MAXN];
bool matchdst[MAXN], visited[MAXN];

void add_edge(int src, int dst) {
dest[e] = dst;
++e;
}

bool go(int src, int dst) {
for (int i = head[src]; i != -1; i = nextid[i]) {
int next = dest[i];
if (next == dst) {
if (matchdst[src]) continue;
matchdst[src] = true;
return true;
}
if (visited[next]) continue;
visited[next] = true;
if (go(match[next], dst)) {
match[next] = src;
return true;
}
}
return false;
}
bool check(int src, int dst) {
REP(i, n) match[i] = i;
CLR(matchdst, 0);
REP(i, 3) {
CLR(visited, 0);
if (!go(src, dst)) return false;
}
return true;
}
bool go(void) {
for (int i = 1; i < n; ++i)
if (!check(0, i) || !check(i, 0))
return false;
return true;
}
int main(int argc, char *argv[]) {
int m, a, b;
while (scanf("%d%d", &n, &m) == 2 && n > 0) {
printf("%s\n", go() ? "YES" : "NO");
}
}

```

Followed by:

User ID:
Title:

Content: