UVA 11045 My T-shirt suits me

发布时间:2016-12-6 16:16:34 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"UVA 11045 My T-shirt suits me",主要涉及到UVA 11045 My T-shirt suits me方面的内容,对于UVA 11045 My T-shirt suits me感兴趣的同学可以参考一下。

又是一个需要拆分点的最大流题目,N件T恤,共种大小,每种数目一致为N/6,分给M个人,其中每个人可以选6个尺寸中的一种,问最后能否每个人分到一件衣服。 分析: 对每个人1~M,建立一条从源点0出发的边,容量为1,然后将每种尺寸拆分为两个点,对每个人分别建立到可选的两个尺寸的边,容量为inf,每个尺寸拆分后建立边的容量为衣服数目N/6,最后每个尺寸建立到汇点的无穷容量的边。 代码: #include <cstdio> #include <cstring> #include <cstdlib> #include <vector> #include <iostream> #include <cctype> #include <queue> #include <algorithm> #include <cmath> #define esp 1e-6 #define inf 0x0f0f0f0f #define print(a) printf("%d\n", (a)); #define bug puts("(****"); #define judge freopen("in.txt","r",stdin); using namespace std; #define N 100 #define M 1000 char *si[]={"XXL","XL","L","M","S","XS"}; struct EDGE { int i, c; EDGE *next, *ani; } *Edge[N], E[M]; int Dfn[N], Now[N], cnt; int src, sink; int n, m; int f(char *s) { for(int i = 0; i < 6; i++) if(!strcmp(s,si[i])) return i; } void add(int i, int j, int c, EDGE &e1, EDGE &e2) { e1.i = j, e1.c = c, e1.next = Edge[i], e1.ani = &e2, Edge[i] = &e1; e2.i = i, e2.c = 0, e2.next = Edge[j], e2.ani = &e1, Edge[j] = &e2; } void init(void) { memset(Edge, 0, sizeof(Edge)); cnt = 0; } int ISAP(int s, int end, int flow) { if(s == end) return flow; int i, tab = n -1, now = 0, vary; for(EDGE *p = Edge[s]; p && flow - now; p = p->next) if(p->c) { if(Dfn[s] == Dfn[i = p->i] + 1) vary = ISAP(i, end, min(flow - now, p->c)), p->c -= vary, p->ani->c += vary, now +=vary; if(p->c) tab = min(tab, Dfn[i]); if(Dfn[src] == n) return now; } if(now == 0) { if(--Now[Dfn[s]] == 0) Dfn[src] = n; Now[Dfn[s] = tab + 1]++; } return now; } int max_flow(int s, int end) { memset(Dfn, 0, sizeof(Dfn)); memset(Now, 0, sizeof(Now)); Now[0] = n; int ret = 0; for(; Dfn[s] < n;) ret += ISAP(s, end, inf); return ret; } char a[10],b[10]; int main(void) { int T; for(int t = scanf("%d", &T); t <= T; t++) { init(); scanf("%d%d", &n, &m); int c = n /6; n = 14 + m; for(int u = m + 1; u <= m + 6; u ++) { int v = u + 6; add(u, v, c, E[cnt], E[cnt + 1]); cnt += 2; add(v, m + 13, inf, E[cnt], E[cnt + 1]); cnt += 2; } for(int i = 1; i <= m; i++) { scanf("%s%s", a, b); int u = f(a); int v = f(b); u += m + 1; v += m + 1; add(i, u, inf, E[cnt], E[cnt + 1]); cnt += 2; add(i, v, inf, E[cnt], E[cnt + 1]); cnt += 2; add(0, i, 1, E[cnt], E[cnt + 1]); cnt += 2; } src = 0, sink = m + 13; int ans = max_flow(src, sink); puts(ans != m ? "NO" : "YES"); } return 0; }

上一篇:Android http请求代码
下一篇:拓扑排序

相关文章

相关评论