程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> UVA 11045 My T-shirt suits me (二分圖)

UVA 11045 My T-shirt suits me (二分圖)

編輯：C++入門知識

UVA 11045 My T-shirt suits me (二分圖)

My T-shirt suits me

Our friend Victor participates as an instructor in an environmental volunteer program. His boss asked Victor to distribute N T-shirts to Mvolunteers, one T-shirt each volunteer, where N is multiple of six, and NM. There are the same number of T-shirts of each one of the six available sizes: XXL, XL, L, M , S, and XS. Victor has a little problem because only two sizes of the T-shirts suit each volunteer.

You must write a program to decide if Victor can distribute T-shirts in such a way that all volunteers get a T-shirt that suit them. If N M, there can be some remaining T-shirts.

Input

The first line of the input contains the number of test cases. For each test case, there is a line with two numbers N and M. N is multiple of 6, 1N36, and indicates the number of T-shirts. Number M, 1M30, indicates the number of volunteers, with NM. Subsequently, M lines are listed where each line contains, separated by one space, the two sizes that suit each volunteer (XXL, XL, L, M , S, or XS).

Output

For each test case you are to print a line containing YES if there is, at least, one distribution where T-shirts suit all volunteers, or NO, in other case.

Sample Input

 
3
18 6
L XL
XL L
XXL XL
S XS
M S
M L
6 4
S XL
L S
L XL
L XL
6 1
L M

Sample Output

 
YES
NO
YES

題意：

有n(n是6的倍數)件衣服，6種尺碼，每種尺碼的衣服數量相同，有m個人，每人有兩種能穿的尺碼，問每個人是否都有衣服穿。

分析：

顯然的二分圖。每個人向其合適的尺碼連邊，容量為1;增加源點和匯點，源點向每個人連邊，容量為1,每種尺碼向匯點連邊，容量為該種尺碼衣服的數量(n/6)。在上圖中跑最大流，如果滿流則所有人都有衣服穿。

/*
 *
 *	Author	:	fcbruce
 *
 *	Date	:	2014-09-04 20:47:21 
 *
 */
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#define sqr(x) ((x)*(x))
#define LL long long
#define itn int
#define INF 0x3f3f3f3f
#define PI 3.1415926535897932384626
#define eps 1e-10

#ifdef _WIN32
	#define lld %I64d
#else
	#define lld %lld
#endif

#define maxm 233
#define maxn 64

using namespace std;

int fir[maxn];
int u[maxm],v[maxm],cap[maxm],flow[maxm],nex[maxm];
int e_max;
int iter[maxn],q[maxn],lv[maxn];

void add_edge(int _u,int _v,int _w)
{
    int e;
    e=e_max++;
    u[e]=_u;v[e]=_v;cap[e]=_w;
    nex[e]=fir[u[e]];fir[u[e]]=e;
    e=e_max++;
    u[e]=_v;v[e]=_u;cap[e]=0;
    nex[e]=fir[u[e]];fir[u[e]]=e;
}

void dinic_bfs(int s)
{
    int f,r;
    memset(lv,-1,sizeof lv);
    q[f=r=0]=s;
    lv[s]=0;
    while(f<=r)
    {
        int x=q[f++];
        for (int e=fir[x];~e;e=nex[e])
        {
            if (cap[e]>flow[e] && lv[v[e]]<0)
            {
                lv[v[e]]=lv[u[e]]+1;
                q[++r]=v[e];
            }
        }
    }
}

int dinic_dfs(int _u,int t,int _f)
{
    if (_u==t)  return _f;
    for (int &e=iter[_u];~e;e=nex[e])
    {
        if (cap[e]>flow[e] && lv[_u]0)
            {
                flow[e]+=_d;
                flow[e^1]-=_d;
                return _d;
            }
        }
    }

    return 0;
}

int max_flow(int s,int t)
{

    memset(flow,0,sizeof flow);
    int total_flow=0;

    for (;;)
    {
        dinic_bfs(s);
        if (lv[t]<0)    return total_flow;
        memcpy(iter,fir,sizeof iter);
        int _f;

        while ((_f=dinic_dfs(s,t,INF))>0)
            total_flow+=_f;
    }

    return total_flow;
}

char _size[7][5]={ ,XS,S,M,L,XL,XXL};

int main()
{
	#ifdef FCBRUCE
		freopen(/home/fcbruce/code/t,r,stdin);
	#endif // FCBRUCE
	
	int T_T;
	int n,m;
	
	scanf( %d,&T_T);
	while (T_T--)
	{
		e_max=0;
		memset(fir,-1,sizeof fir);
		
		scanf( %d%d,&n,&m);
		
		int s=0,t=m+7;
		
		char s1[5],s2[5];
		
		for (int i=0;i