首页 > ACM题库 > HDU-杭电 > HDU 4560-我是歌手-网络流-[解题报告]HOJ
2015
07-25

HDU 4560-我是歌手-网络流-[解题报告]HOJ

我是歌手

问题描述 :

2013年一开始,一档音乐节目“我是歌手”就惊艳了大家一回。闲话少说,现在,你成为了这档节目的总导演,你的任务很简单,安排每一期节目的内容。

现在有N个歌手,M种歌曲流派(Rock,Pop之类),每个歌手都有自己擅长的流派领域,这些资料都已整理好。你的工作是,安排尽可能多场的演唱比赛。每一场比赛所有歌手都必须上场,为了提高收视率,每个人演唱的歌曲类型不能相同,即便一些歌手要被迫选择一些他们不擅长的。同时,为了展现全面性,在不同的演唱比赛上,每个歌手都会安排不同的歌曲流派。

但是问题是,对于任何一个歌曲流派的歌迷,如果超过K个不擅长的歌手演唱了这种歌曲,他们就会表示不满,比如,发一些宣泄不满的帖子微博,为了表示观点挑起事端等等。你当然不希望这些事情与你的节目有关,在这个前提下,你可以任意安排尽可能多的比赛场次。

输入:

输入第一行为T,表示有T组测试数据。
每组数据以四个数字N,M,L, K开始。L表示有L组擅长关系,接下来的L行,每一行有两个数字Ai,Bi,表示歌手Ai擅长Bi类型的歌曲。

[Technical Specification]

1. 1 <= T <= 100
2. 1 <= N <= M <= 74, 0 <= K <= N
3. 0 <= L <= N*M
4. 1 <= Ai <= N, 1 <= Bi <= M, 相同关系不会重复出现

输出:

输入第一行为T,表示有T组测试数据。
每组数据以四个数字N,M,L, K开始。L表示有L组擅长关系,接下来的L行,每一行有两个数字Ai,Bi,表示歌手Ai擅长Bi类型的歌曲。

[Technical Specification]

1. 1 <= T <= 100
2. 1 <= N <= M <= 74, 0 <= K <= N
3. 0 <= L <= N*M
4. 1 <= Ai <= N, 1 <= Bi <= M, 相同关系不会重复出现

样例输入:

3
1 1 1 0
1 1
1 3 0 1
3 3 5 1
1 1
1 2
2 2
2 3
3 1

样例输出:

Case 1: 1
Case 2: 3
Case 3: 2

Hint
对第三组样例,可以如此安排: 第一场三位歌手分别演唱(2,3,1)类型的歌曲,第二场分别演唱(1,2,3)。 这样只有类型3被不擅长的歌手演唱过1次,挑剔的歌迷观众还可以接受。

题意:2013年一开始,一档音乐节目“我是歌手”就惊艳了大家一回。闲话少说,现在,你成为了这档节目的总导演,你的任务很简单,安排每一期节目的内容。

现在有N个歌手,M种歌曲流派(Rock,Pop之类),每个歌手都有自己擅长的流派领域,这些资料都已整理好。你的工作是,安排尽可能多场的演唱比赛。每一场比赛所有歌手都必须上场,为了提高收视率,每个人演唱的歌曲类型不能相同,即便一些歌手要被迫选择一些他们不擅长的。同时,为了展现全面性,在不同的演唱比赛上,每个歌手都会安排不同的歌曲流派。

但是问题是,对于任何一个歌曲流派的歌迷,如果超过K个不擅长的歌手演唱了这种歌曲,他们就会表示不满,比如,发一些宣泄不满的帖子微博,为了表示观点挑起事端等等。你当然不希望这些事情与你的节目有关,在这个前提下,你可以任意安排尽可能多的比赛场次。


想法:没得说这题是网络流,就是看怎么建图,设最大的场次为tim,我们知道,0<=tim<=歌曲流派数,因为每一次每个歌手唱的不一样。

建图:虚拟超级原点source和汇点sink。

1.s到每一个歌手i连一条容量为tim的边:显然每个歌手是要参加tim场演唱的;

2.每一个歌手i向他擅长的歌曲流派k连一条容量为1的边:他只能一场唱一次;

3.每一个歌手i向他不擅长的歌曲流派k‘连一条容量为1的边:它可以唱不擅长的,但是还是只能唱一首歌;

4.k’到k连一条容量为K(题中的K,大写):限制一条歌手唱不擅长的歌曲流派的人数,当人数>K的时候,显然只能流过去K个人;

5.k到sink连一条容量为tim的边:是对唱这个歌曲流派的总人数(包括擅长的歌手也包括不擅长的歌手)的限制。


#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#define inf 0x7fffffff
using namespace std;
const int nodes=300;
const int edges=180000;
int n,m,l,k;
int map[80][80];
int s,t;
struct node 
{
	int v,next;
	int flow;
}e[edges];
int head[nodes],cnt;
class Dinic
{
    public:
        int spath()
        {
            queue<int>q;
            while(!q.empty()) q.pop();
            memset(dis,-1,sizeof(dis));
            dis[s]=0;
            q.push(s);
            while(!q.empty())
            {
                int u=q.front();
                q.pop();
                for(int i=head[u];i+1;i=e[i].next)
                {
                    int v=e[i].v;
                    if(dis[v]==-1&&e[i].flow>0)
                    {
                        dis[v]=dis[u]+1;
                        q.push(v);
                    }
                }
            }
            return dis[t]!=-1;
        }
        int Min(int a,int b)
        {
            if(a<b) return a;
            return b;
        }
        int dfs(int u,int flow)
        {
            int cost=0;
            if(u==t) return flow;
            for(int i=head[u];i+1;i=e[i].next)
            {
                int v=e[i].v;
                if(dis[v]==dis[u]+1&&e[i].flow>0)
                {
                    int min=dfs(v,Min(e[i].flow,flow-cost));
                    if(min>0)
                    {
                        e[i].flow-=min;
                        e[i^1].flow+=min;
                        cost+=min;
                        if(cost==flow) break;
                    }
                    else dis[v]=-1;
                }
            }
            return cost;
        }
        int result()
        {
            int res=0;
            while(spath())
            {
                res+=dfs(s,inf);
            }
            return res;
        }
    private:
        int dis[nodes];
}dinic;
void Init()
{
	memset(head,-1,sizeof(head));
	cnt=0;
}
void add(int a,int b,int c)
{
	e[cnt].v=b;
	e[cnt].next=head[a];
	e[cnt].flow=c;
	head[a]=cnt++;
	
	e[cnt].v=a;
	e[cnt].next=head[b];
	e[cnt].flow=0;
	head[b]=cnt++;
}
void Input()
{
	scanf("%d%d%d%d",&n,&m,&l,&k);
	memset(map,0,sizeof(map));
	for(int i=1;i<=l;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		map[a][b]=1;
	}
}
bool judge(int tim)
{
	s=0;t=2*m+n+1;
	Init();
	for(int i=1;i<=n;i++)
	add(s,i,tim);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(map[i][j]) add(i,n+j,1);
			else add(i,n+m+j,1);
		}
	}
	for(int i=1;i<=m;i++)
	{
		add(n+m+i,n+i,k);
		add(n+i,t,tim);
	}
	int k=dinic.result();
	if(k>=tim*n) return true;
	else return false;
}
void treatment(int ca)
{
	int ans;
	int low=0,up=m;
	while(low<=up)
	{
		int mid=(low+up)/2;
		if(judge(mid))
		{
			ans=mid;
			low=mid+1;
		}
		else up=mid-1;
	}
	printf("Case %d: %d\n",ca,ans);
} 
int main()
{
	int t,ca=1;
	scanf("%d",&t);
	while(t--)
	{
		Input();
		treatment(ca++);
	}
	return 0;
}



版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/triple_wdf/article/details/49286229