題意

現在要將5種型號的衣服分發給n個參賽者,然后給出每個參賽者所需要的衣服的尺碼的大小范圍,在該尺碼范圍內的衣服該選手可以接受,再給出這5種型號衣服各自的數量,問是否存在一種分配方案使得每個選手都能夠拿到自己尺碼范圍內的衣服.

思路

明顯的二分圖多重最大匹配問題：每個點能匹配的邊不再限制1個，而是多個。 做法：最大流。雖說也有對應的匈牙利算法，但是我還是圖省事用最大流做了。 建圖：源點連接每個型號的衣服，容量為能夠匹配的個數（數量），匯點連接每個隊員，容量也為能夠匹配的個數（1），其他匹配邊容量為1。

代碼

? #include #include #include #include #include #include #include #define MID(x,y) ((x+y)/2) #define mem(a,b) memset(a,b,sizeof(a)) using namespace std; const int MAXV = 35; const int MAXE = 205; const int oo = 0x3fffffff;template struct Dinic{struct flow_node{int u, v;T flow;int opp;int next;}arc[2*MAXE];int vn, en, head[MAXV];int cur[MAXV];int q[MAXV];int path[2*MAXE], top;int dep[MAXV];void init(int n){vn = n;en = 0;mem(head, -1);}void insert_flow(int u, int v, T flow){arc[en].u = u;arc[en].v = v;arc[en].flow = flow;arc[en].next = head[u];head[u] = en ++;arc[en].u = v;arc[en].v = u;arc[en].flow = 0;arc[en].next = head[v];head[v] = en ++;}bool bfs(int s, int t){mem(dep, -1);int lq = 0, rq = 1;dep[s] = 0;q[lq] = s;while(lq < rq){int u = q[lq ++];if (u == t){return true;}for (int i = head[u]; i != -1; i = arc[i].next){int v = arc[i].v;if (dep[v] == -1 && arc[i].flow > 0){dep[v] = dep[u] + 1;q[rq ++] = v;}}}return false;}T solve(int s, int t){T maxflow = 0;while(bfs(s, t)){int i, j;for (i = 1; i <= vn; i ++) cur[i] = head[i];for (i = s, top = 0;;){if (i == t){int mink;T minflow = 0x7fffffff; //要比容量的oo大for (int k = 0; k < top; k ++)if (minflow > arc[path[k]].flow){minflow = arc[path[k]].flow;mink = k;}for (int k = 0; k < top; k ++)arc[path[k]].flow -= minflow, arc[path[k]^1].flow += minflow;maxflow += minflow;top = mink;i = arc[path[top]].u;}for (j = cur[i]; j != -1; cur[i] = j = arc[j].next){int v = arc[j].v;if (arc[j].flow && dep[v] == dep[i] + 1)break;}if (j != -1){path[top ++] = j;i = arc[j].v;}else{if (top == 0) break;dep[i] = -1;i = arc[path[-- top]].u;}}}return maxflow;} }; Dinic dinic;int main(){//freopen("test.in", "r", stdin);//freopen("test.out", "w", stdout);string s;while(cin >> s){if (s == "ENDOFINPUT")break;int n;cin >> n;dinic.init(n+7);for (int i = 1; i <= n; i ++){string tmp;cin >> tmp;dinic.insert_flow(i+5, n+7, 1);for (int j = 0; j < (int)tmp.size(); j ++){switch (tmp[j]){case 'S':dinic.insert_flow(1, i+5, 1);case 'M':dinic.insert_flow(2, i+5, 1);case 'L':dinic.insert_flow(3, i+5, 1);case 'X':dinic.insert_flow(4, i+5, 1);case 'T':dinic.insert_flow(5, i+5, 1);break;}}}for (int i = 1; i <= 5; i ++){int num;cin >> num;dinic.insert_flow(n+6, i, num);}if (dinic.solve(n+6, n+7) == n){puts("T-shirts rock!");}else{puts("I'd rather not wear a shirt anyway...");}cin >> s;}return 0; }

轉載于:https://www.cnblogs.com/AbandonZHANG/p/4114074.html

總結

以上是生活随笔為你收集整理的POJ 2584 T-Shirt Gumbo (二分图多重最大匹配)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。