242 Students Morning

题目大意:

有有的人可以不去学校,只要满足每个学校有个人每个人都去上学,,比如可以在家浪。。。。。。

解题思路:

首先这道题目显然可以用有上下确界的可行流做,但是太麻烦了,直接跑最大流就行了啊。 首先原点连一条流量为说明是可行的,否则是不行的。

AC代码:;int G[510][510]={{0}};int f[510][510]={{0}};int N,K;int st=0,en;int dist[510]={0};int dui[510]={0};int duip=0;void bfs(){duip=0;dui[++duip]=en;for(int i=1;i<=duip;i++){int u=dui[i];for(int v=0;v<=en;v++){if(G[v][u]-f[v][u]>0 && dist[v]>dist[u]+1){dist[v]=dist[u]+1;dui[++duip]=v;}}}return;}int Max_Flow(int now,int Max){if(now==en) return Max;int sum=0;for(int i=0;i<=en;i++){if(G[now][i]-f[now][i]>0 && dist[now]==dist[i]+1){int tmp=Min(G[now][i]-f[now][i],Max);tmp=Max_Flow(i,tmp);sum+=tmp;Max-=tmp;f[now][i]+=tmp;f[i][now]-=tmp;if(Max==0) return sum;}}return sum;}void prt(){for(int i=N+1;i<=en-1;i++){printf(“2 “);for(int j=1;j<=N;j++)if(f[j][i]==1)printf(“%d “,j);puts(“”);}return;}int main(){scanf(“%d%d”,&N,&K);en=N+K+1;for(int i=1;i<=N;i++){int num=0;scanf(“%d”,&num);for(int j=1;j<=num;j++){int sb;scanf(“%d”,&sb);G[i][sb+N]=1;}G[st][i]=1;}for(int i=1;i<=K;i++)G[i+N][en]=2;int ans=0;for(;;){memset(dist,0x3f3f3f3f,sizeof(dist));dist[en]=0;bfs();if(dist[st]==0x3f3f3f3f)break;ans+=Max_Flow(st,2e9);if(ans==K*2) break;}if(ans!=K*2)cout<<“NO”<<endl;else{cout<<“YES”<<endl;prt();}return 0;}

绚丽的民族风情,悠久的历史文化。抛开尘世的纷扰,

242 Students Morning

相关文章:

你感兴趣的文章:

标签云: