「codecomb2092」课程选择

大学选课总是烦恼着很多人。现在X同学选出了很多备选课，但是有的课程之间是有时间冲突的。X不会分身，自然无法在同一个时间上不同的课。每个课可能有很多备选时间，但是每个课只需要选一个时间上就可以了。当然X没有必要在不同时间上相同的课。

现在把X的备选课及相应的上课时间告诉你，请你求出X一星期最多可以上多少课。

输入格式

第一行输入一个n，表示X将提供给你n个备选课。

接下来n行，每行包含若干个整数来描述每个备选课信息。

对于第i行，首先读入一个k，表示第i个备选课有k个时间可以选择。接下来读入k对数p，q，表示在第i个备选课在星期p的第q节课可以上。

输出格式

输出仅包含一个整数，表示X最多可以选多少节课来上。

样例数据 1

输入　 [复制]

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

输出

4

备注

对于100%的数据：n<=300，1<=t<=84，1<=p<=7，1<=q<=12。

题解

网络流水过

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cstring>
#define inf 1000000000
#define ll long long
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m,cnt=1,ans,T;
struct edge{int to,next,v;}e[200005];
int h[1005],last[1005],q[1005];
bool vis[1005];
void insert(int u,int v,int w)
{
	e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].v=w;
	e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;e[cnt].v=0;
}
bool bfs()
{
	int head=0,tail=1;
	for(int i=1;i<=T;i++)h[i]=-1;
	q[0]=0;h[0]=0;
	while(head!=tail)
	{
		int now=q[head];head++;
		for(int i=last[now];i;i=e[i].next)
			if(e[i].v&&h[e[i].to]==-1)
			{
				h[e[i].to]=h[now]+1;
				q[tail++]=e[i].to;
			}
	}
	return h[T]!=-1;
}
int dfs(int x,int f)
{
	if(x==T)return f;
	int w,used=0;
	for(int i=last[x];i;i=e[i].next)
		if(h[e[i].to]==h[x]+1)
		{
			w=f-used;
			w=dfs(e[i].to,min(e[i].v,w));
			e[i].v-=w;e[i^1].v+=w;
			used+=w;if(used==f)return f;
		}
	if(!used)h[x]=-1;
	return used;
}
void dinic()
{
	while(bfs())ans+=dfs(0,inf);
}
int main()
{
	n=read();T=n+85;
	for(int i=1;i<=n;i++)
		insert(0,i,1);
	for(int i=1;i<=84;i++)
		insert(i+n,T,1);
	for(int i=1;i<=n;i++)
	{
		int k=read();
		while(k--)
		{
			int p=read(),q=read();
			int t=(p-1)*12+q+n;
			insert(i,t,1);
		}
	}
	dinic();
	printf("%d",ans);
	return 0;
}

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<algorithm>

#include<cmath>

#include<cstring>

#define inf 1000000000

#define ll long long

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,m,cnt=1,ans,T;

struct edge{int to,next,v;}e[200005];

int h[1005],last[1005],q[1005];

bool vis[1005];

void insert(int u,int v,int w)

{

e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].v=w;

e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;e[cnt].v=0;

}

bool bfs()

{

int head=0,tail=1;

for(int i=1;i<=T;i++)h[i]=-1;

q[0]=0;h[0]=0;

while(head!=tail)

{

int now=q[head];head++;

for(int i=last[now];i;i=e[i].next)

if(e[i].v&&h[e[i].to]==-1)

{

h[e[i].to]=h[now]+1;

q[tail++]=e[i].to;

}

return h[T]!=-1;

}

int dfs(int x,int f)

{

if(x==T)return f;

int w,used=0;

for(int i=last[x];i;i=e[i].next)

if(h[e[i].to]==h[x]+1)

{

w=f-used;

w=dfs(e[i].to,min(e[i].v,w));

e[i].v-=w;e[i^1].v+=w;

used+=w;if(used==f)return f;

}

if(!used)h[x]=-1;

return used;

}

void dinic()

{

while(bfs())ans+=dfs(0,inf);

}

int main()

{

n=read();T=n+85;

for(int i=1;i<=n;i++)

insert(0,i,1);

for(int i=1;i<=84;i++)

insert(i+n,T,1);

for(int i=1;i<=n;i++)

{

int k=read();

while(k--)

{

int p=read(),q=read();

int t=(p-1)*12+q+n;

insert(i,t,1);

}

dinic();

printf("%d",ans);

return 0;

}

hzwer.com _ Home | http://hzwer.com

题目描述

输入格式

输出格式

样例数据 1

备注

分类目录

热门文章

Myfriends

近期评论