首页 > 代码库 > UVA 11045 My T-shirt suits me
UVA 11045 My T-shirt suits me
一开始就想到网络流。。后来一想暴力能不能过。自己写的T了。看了别人有暴力过的。
暴力的思路就是6进制数字表示给予的衣服的数量。然后每个人的需求表示成01 的6位串然后爆搜。
网络流就建一个源一个汇 然后针对输入 i - i + 6 边权为N/6； 然后M个人由衣服连M个人边权为1。与源直接相连的点就INF求最大流值判断即可。
别人的建图更简单一些。不需要设置INF；思路一样
#include <map>#include <set>#include <list>#include <cmath>#include <ctime>#include <deque>#include <stack>#include <queue>#include <cctype>#include <cstdio>#include <string>#include <vector>#include <climits>#include <cstdlib>#include <cstring>#include <iostream>#include <algorithm>#define LL long long#define PI 3.1415926535897932626using namespace std;int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);}int src,tag;int N,M;const int INF = 0x3f3f3f3f ;char size[10][20] = {"xxa","XXL","XL","L","M","S","XS"};int d[100],cap[100][100];bool inq[100];int flow[100][100];int p[100];void read(){ scanf("%d%d",&N,&M); N /= 6; memset(cap,0,sizeof(cap)); for (int i = 1; i <= 6; i++) { cap[0][i] = INF; cap[i][i + 6] = N; } for (int j = 1; j <= M; j++) { char a[8],b[8]; scanf("%s%s",a,b); int s1 = -1, s2; for (int i = 1; i <= 6; i++) { if (strcmp(size[i],a) == 0) s1 = i; if (strcmp(size[i],b) == 0) s2 = i; } //printf("%d %d\n",s1,s2); cap[s1 + 6][12 + j] = 1; cap[s2 + 6][12 + j] = 1; cap[12 + j][12 + M + 1] = 1; } src = 0; tag = 12 + M + 1;}int Edmons_karp(){ queue<int>q; int a[100]; while (!q.empty()) q.pop(); memset(flow,0,sizeof(flow)); int ans = 0; while (true) { memset(a,0,sizeof(a)); a[src] = INF; q.push(src); while(!q.empty()) { int u = q.front(); q.pop(); for (int v = 1; v <= tag; v++) if (!a[v] && cap[u][v] > flow[u][v]) { p[v] = u; q.push(v); a[v] = min(a[u],cap[u][v] - flow[u][v]); } } if (a[tag] == 0) break; for (int u = tag; u != src; u = p[u]) { flow[p[u]][u] += a[tag]; flow[u][p[u]] -= a[tag]; } ans += a[tag]; } return ans;}int main(){ //freopen("sample.txt","r",stdin); int T; scanf("%d",&T); while (T--) { read(); int ans = Edmons_karp(); //printf("%d\n",ans); if (ans >= M) printf("YES\n"); else printf("NO\n"); } return 0;}
TLE 的代码也贴一下吧
#include <map>#include <set>#include <list>#include <cmath>#include <ctime>#include <deque>#include <stack>#include <queue>#include <cctype>#include <cstdio>#include <string>#include <vector>#include <climits>#include <cstdlib>#include <cstring>#include <iostream>#include <algorithm>#define LL long long#define PI 3.1415926535897932626using namespace std;int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);}int st[32];int N,M;bool found;char size[10][20] = {"XXL","XL","L","M","S","XS"};int res;void read(){ res = 0; scanf("%d%d",&N,&M); N /= 6; char tmp[10]; for (int i = 0; i < 6 ; i++) tmp[i] = N + ‘0‘; tmp[6] = ‘\0‘; sscanf(tmp,"%d",&res); memset(st,0,sizeof(st)); for (int i = 1; i <= M; i++) { char a[6],b[6]; scanf("%s%s",a,b); int j; for (j = 0; j < 6; j++) if (strcmp(a,size[j]) == 0) break; st[i] |= 1 << j; for (j = 0; j < 6; j++) if (strcmp(b,size[j]) == 0) break; st[i] |= 1 << j; }}void calcu(int cur, int sta, int cnt){ if (found) return ; if (cnt >= M) { found = true; return ; } int temp = sta; bool change = false; char str[20]; for (int i = cur; i <= M; i++) { int a = -1,b = -1; for (int j = 0; j < 6; j++) { if (st[i] & (1 << j)) { if (a == -1) { a = j; } else b = j; } } sprintf(str,"%d",temp); if (str[a] - ‘0‘ > 0) { change = true; str[a]--; sscanf(str,"%d",&temp); calcu(cur + 1, temp, cnt + 1); str[a]++; } temp = sta; if (str[b] - ‘0‘ > 0) { change = true; str[b]--; sscanf(str,"%d",&temp); calcu(cur + 1, temp, cnt + 1); str[b]++; } if (!change) return ; }}int main(){ //freopen("sample.txt","r",stdin); int T; scanf("%d",&T); while (T--) { found = false; read(); calcu(1,res,0); if (found) printf("YES\n"); else printf("NO\n"); } return 0;}
UVA 11045 My T-shirt suits me
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。