POJ 1698(이분 도의 다 중 일치)

전송:http://www.cppblog.com/MatoNo1/archive/2011/03/26/142766.aspx
 
우 리 는 한 그림 에서 점 마다 한 변 만 일치 할 수 있 는 상황 이 2 분 그림 의 가장 큰 일치 문제 라 는 것 을 알 고 있 습 니 다.그러나 또 다른 상황 은 점 마다 여러 변 을 일치 시 킬 수 있 지만 상한 선 이 있 습 니 다.L.즉,Li 는 가장 많은 점 i 가 Li 변 과 관련 이 있다 고 가정 합 니 다.
2 분 그림 의 최대 일치:
1.원점 S 와 어 셈 블 리 T 를 만 듭 니 다.
2.S 는 x 정점 을 가리 키 고 용량 은 x 내 점 의 L 값 이다.y 정점 은 T 를 가리 키 며 용량 은 y 내 점 의 L 값 이다.
3.원 그림 의 각 변 은 새 그림 에 존재 하고 용량 은 1 이다.
그러면 S 에서 T 까지 의 최대 흐름 은 다 중 최대 일치 입 니 다.
 
예 를 들 어 POJ 1698.
 

 1 #include <cstdio>

 2 #include <cstring>

 3 #include <queue>

 4 #define _clr(x, y) memset(x, y, sizeof(x))

 5 #define Min(x, y) (x < y ? x : y)

 6 #define Max(x, y) (x > y ? x : y)

 7 #define INF 0x3f3f3f3f

 8 #define N 400

 9 using namespace std;

10 

11 int edge[N][N], dist[N];

12 int T, S, Sum, n;

13 bool used[N];

14 

15 bool bfs()

16 {

17     _clr(dist, -1);

18     queue<int> Q;

19     dist[S] = 0;

20     Q.push(S);

21     while(!Q.empty())

22     {

23         int u = Q.front();

24         Q.pop();

25         for(int v=0; v<=T; v++)

26         {

27             if(edge[u][v] && dist[v]<0)

28             {

29                 dist[v] = dist[u] + 1;

30                 Q.push(v);

31             }

32         }

33     }

34     return dist[T]>0? 1 : 0;

35 }

36 

37 int dfs(int u, int alpha)

38 {

39     int a;

40     if(u==T) return alpha;

41     for(int i=0; i<=T; i++)

42     {

43         if(edge[u][i] && dist[i]==dist[u]+1 && (a=dfs(i, Min(alpha, edge[u][i]))))

44         {

45             edge[u][i] -= a;

46             edge[i][u] += a;

47             return a;

48         }

49     }

50     dist[u] = -1;

51     return 0;

52 }

53 void Dinic()

54 {

55     int ans=0, a=0;

56     while(bfs())

57         while(a=dfs(0, INF)) ans += a;

58     printf ("%s
", ans==Sum ? "Yes" : "No");

59 }

60 

61 int main()

62 {

63     int K, week[10];

64     scanf("%d", &K);

65     while(K--)

66     {

67         int day = 0, d, w;

68         scanf("%d", &n);

69         Sum = 0, S=0;

70         _clr(week, 0);

71         _clr(edge, 0);

72         for(int i=1; i<=n; i++)    // 1--n      ,n+1---T      !

73         {

74             for(int i1=0; i1<7; i1++) scanf("%d", week+i1);

75             scanf("%d%d", &d, &w);

76             day = Max(day, w);

77             edge[S][i] = d;     //           x                   .

78             Sum += d;

79 

80             for(int j=0; j<w; j++) // W     .

81             {

82                 for(int k=0; k<7; k++)

83                     if(week[k])

84                         edge[i][n+j*7+k+1] = 1;    // i      w    k  .

85             }

86             T = day*7+n+1;

87             for(int i=n+1; i<T; i++)

88                 edge[i][T] = 1;

89         }

90         Dinic();

91     }

92     return 0;

93 }