POJ2584 T-Shirt Gumbo 二分圖匹配（網絡流），poj2584gumbo
![]()
1 #include <cstdio>
2 #include <cstring>
3 #include <algorithm>
4
5 const int inf=0x3f3f3f3f;
6 const int sink=30;
7
8 struct Edge
9 {
10 int to;
11 int next;
12 int capacity;
13
14 void assign(int t,int n,int c)
15 {
16 to=t; next=n; capacity=c;
17 }
18 };
19
20 Edge edgeList[2048];
21 int head[40];
22 int edgeCnt=0;
23
24 inline void init()
25 {
26 edgeCnt=0;
27 memset(head,-1,sizeof(head));
28 }
29
30 char cmd[20];
31 int X;
32
33 inline int idx(char s)
34 {
35 switch(s)
36 {
37 case 'S': return 1;
38 case 'M': return 2;
39 case 'L': return 3;
40 case 'X': return 4;
41 case 'T': return 5;
42 default : return -1;
43 }
44 }
45
46 inline void addEdge(int v1,int v2,int c)
47 {
48 edgeList[edgeCnt].assign(v2,head[v1],c);
49 head[v1]=edgeCnt++;
50 edgeList[edgeCnt].assign(v1,head[v2],0);
51 head[v2]=edgeCnt++;
52 }
53
54 bool input()
55 {
56 scanf("%s",cmd);
57 if(cmd[0]=='E') return false;
58
59 scanf("%d",&X);
60 for(int i=6;i<=X+5;i++)
61 {
62 scanf("%s",cmd);
63 int sm=idx(cmd[0]);
64 int lg=idx(cmd[1]);
65 for(int j=sm;j<=lg;j++) addEdge(j,i,inf);
66 addEdge(i,sink,1);
67 }
68 for(int i=1;i<=5;i++)
69 {
70 int n; scanf("%d",&n);
71 addEdge(0,i,n);
72 }
73 scanf("%s",cmd);
74 return true;
75 }
76
77 int dist[40];
78
79 #include <queue>
80
81 int bfs()
82 {
83 memset(dist,0,sizeof(dist));
84 dist[0]=1;
85
86 std::queue<int> __bfs;
87 __bfs.push(0);
88
89 while(!__bfs.empty())
90 {
91 int cur=__bfs.front();
92 __bfs.pop();
93
94 for(int e=head[cur];e>-1;e=edgeList[e].next)
95 {
96 int __to=edgeList[e].to;
97 if(edgeList[e].capacity && !dist[__to])
98 {
99 dist[__to]=dist[cur]+1;
100 __bfs.push(__to);
101 }
102 }
103 }
104 return dist[sink];
105 }
106
107 int dinic_aux(int cur,int flow)
108 {
109 if(cur==sink) return flow;
110
111 int res=0;
112 int temp=0;
113 for(int e=head[cur];e>-1;e=edgeList[e].next)
114 {
115 int __to=edgeList[e].to;
116 if(dist[__to]==dist[cur]+1 && edgeList[e].capacity)
117 {
118 temp=dinic_aux(__to,std::min(flow,edgeList[e].capacity));
119 res+=temp;
120 flow-=temp;
121 edgeList[e].capacity-=temp;
122 edgeList[e^1].capacity+=temp;
123 }
124 }
125 return res;
126 }
127
128 inline int dinic()
129 {
130 int res=0;
131 while(bfs()) res+=dinic_aux(0,inf);
132 return res;
133 }
134
135 const char success[]="T-shirts rock!";
136 const char fail[]="I'd rather not wear a shirt anyway...";
137
138 inline void solve()
139 {
140 bool proc=true;
141 while(proc)
142 {
143 init();
144 proc=input();
145 if(proc) printf("%s\n",dinic()==X?success:fail);
146 }
147 }
148
149 int main() { solve(); return 0; }
Using Dinic Algorithm
這道題有兩種解決思路：
（1）拆點。將n件同樣尺碼的T恤拆成n個節點，然後對於每一個分離的節點向對應的人連邊
效率比較低，點的個數最大有可能達到100以上
（2）網絡流。建模的基本思想與一般二分圖匹配的網絡流建模相同，只是從源點向T恤尺碼代表的節點連邊時，載量設為該種T恤的件數
點的個數不超過30，相對比較高效
Appendix：二分圖匹配的網絡流建模：
約定二分圖的兩部分記作A和B
設立一個源點和匯點。源點同A中所有點連邊，載量設為1（表示該點只能在匹配中被選中一次）；匯點同B中所有點連邊，載量也設為1
二分圖中原來的邊保留，令其方向為A→B，載量為任意正整數
對於網絡流問題，邊表是個很不錯的選擇。既能像鄰接表那樣節約空間，又能方便地記錄反向邊。
記正向邊的標號為2x，那麼反向邊的標號就是2x+1，訪問反向邊只需將正向邊的標號xor 1
