题目描述
大学选课总是烦恼着很多人。现在X同学选出了很多备选课,但是有的课程之间是有时间冲突的。X不会分身,自然无法在同一个时间上不同的课。每个课可能有很多备选时间,但是每个课只需要选一个时间上就可以了。当然X没有必要在不同时间上相同的课。
现在把X的备选课及相应的上课时间告诉你,请你求出X一星期最多可以上多少课。
输入格式
第一行输入一个n,表示X将提供给你n个备选课。
接下来n行,每行包含若干个整数来描述每个备选课信息。
对于第i行,首先读入一个k,表示第i个备选课有k个时间可以选择。接下来读入k对数p,q,表示在第i个备选课在星期p的第q节课可以上。
输出格式
输出仅包含一个整数,表示X最多可以选多少节课来上。
样例数据 1
备注
对于100%的数据:n<=300,1<=t<=84,1<=p<=7,1<=q<=12。
比第一题更裸的网络流
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #include<queue> #include<deque> #include<set> #include<map> #include<ctime> #define LL long long #define inf 0x7ffffff #define pa pair<int,int> #define pi 3.1415926535897932384626433832795028841971 #define S 0 #define T 1000 using namespace std; struct edge{ int to,next,v; }e[200010]; int head[10010]; int n,m,cnt=1,t,w,ans; int h[10010]; int q[100010]; inline void ins(int u,int v,int w) { e[++cnt].to=v; e[cnt].v=w; e[cnt].next=head[u]; head[u]=cnt; } inline void insert(int u,int v,int w) { ins(u,v,w); ins(v,u,0); } inline bool bfs() { memset(h,-1,sizeof(h)); t=0;w=1;h[S]=0;q[1]=S; while (t<w) { int now=q[++t]; for(int i=head[now];i;i=e[i].next) if (e[i].v&&h[e[i].to]==-1) { h[e[i].to]=h[now]+1; q[++w]=e[i].to; } } if (h[T]==-1)return 0; return 1; } inline int dfs(int x,int f) { if (x==T||!f)return f; int used=0,w; for (int i=head[x];i;i=e[i].next) if (e[i].v&&h[e[i].to]==h[x]+1) { w=used; w=dfs(e[i].to,min(e[i].v,f-w)); e[i].v-=w; e[i^1].v+=w; used+=w; if (!f)return used; } if (!used)h[x]=-1; return used; } inline void dinic() { while (bfs())ans+=dfs(S,inf); } inline LL read() { LL 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 main() { n=read(); for (int i=1;i<=n;i++) insert(S,i,1); for (int i=n+1;i<=n+84;i++) insert(i,T,1); for (int i=1;i<=n;i++) { int t=read(); for (int j=1;j<=t;j++) { int p=read(),q=read(); int tru=(p-1)*12+q; insert(i,n+tru,1); } } dinic(); printf("%d\n",ans); }