现在的位置: 首页 > 综合 > 正文

UVA 11045 My T-shirt suits me

2012年09月26日 ⁄ 综合 ⁄ 共 1097字 ⁄ 字号 评论关闭

UVA_11045

    这个题目可以用网络流去做。首先,我们抽象出一个源点和一个汇,源点和各种衣服都连一条有向边,容量为N/6,人所对应的衣服和人之间连一条有向边,容量为1,人与汇点之间连一条有向边,容量为1,之后就可以用网络流的方法去解了,如果最后汇点的流量为M,则表示可以,否则就不可以。

#include<string.h>
#include<stdio.h>
int N, M, T;
int flow[110][110], cap[110][110], a[110], q[110], p[110];
char b[][5]={"\0","XXL","XL","L","M","S","XS"};
char b1[5], b2[5];
void init()
{
int i, j, k, a1, a2;
memset(cap, 0, sizeof(cap));
scanf("%d%d", &N, &M);
T = M + 7;
for(i = 1; i <= 6; i ++)
cap[0][i] = N / 6;
for(i = 1; i <= M; i ++)
{
scanf("%s%s", b1, b2);
for(a1 = 1; strcmp(b[a1], b1) != 0; a1 ++);
for(a2 = 1; strcmp(b[a2], b2) != 0; a2 ++);
cap[a1][i + 6] = 1;
cap[a2][i + 6] = 1;
cap[i + 6][T] = 1;
}
}
int check()
{
int i, u, v, f, front, rear;
memset(flow, 0, sizeof(flow));
f = 0;
for(;;)
{
memset(a, 0, sizeof(a));
a[0] = 1000000000;
front = rear = 0;
q[rear ++] = 0;
while(front < rear)
{
u = q[front ++];
for(v = 0; v <= T; v ++)
if(!a[v] && flow[u][v] < cap[u][v])
{
p[v] = u;
a[v] = a[u];
if(cap[u][v] - flow[u][v] < a[v])
a[v] = cap[u][v] - flow[u][v];
q[rear ++] = v;
}
}
if(a[T] == 0)
break;
for(u = T; u != 0; u = p[u])
{
flow[p[u]][u] += a[T];
flow[u][p[u]] -= a[T];
}
f += a[T];
}
if(f == M)
return 1;
else
return 0;
}
int main()
{
int i, j, k, t;
scanf("%d", &t);
while(t --)
{
init();
if(check())
printf("YES\n");
else
printf("NO\n");
}
return 0;
}


抱歉!评论已关闭.