求dalao差错
查看原帖
求dalao差错
230804
Durancer楼主2021/2/5 17:06

输入完了但是不运行QAQ

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#include<algorithm>
#include<map>
using namespace std;
const int N=29;
const int M=1e4+9;
const int inf=2e9+9;
struct node{
	int last;
	int to;
	int c;
}e[M];
int head[N];
int cur[N];
int d[N];
int s,t,n,k,cnt,tol;
int type[N];//每个类型需要几个
void add(int from,int to,int dis)
{
	e[++cnt].last=head[from];
	e[cnt].to=to;
	e[cnt].c=dis;
	head[from]=cnt;
}
bool bfs()
{
	memset(d,-1,sizeof(d));
	queue<int> q;
	q.push(s);
	cur[s]=head[s];
	d[s]=0;
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int i=head[u];i;i=e[i].last)
		{
			int v=e[i].to;
			int w=e[i].c;
			if(w&&d[v]==-1)
			{
				d[v]=d[u]+1;
				cur[v]=head[v];
				q.push(v);
				if(v==t) return true;
			}
		}
	}
	return false;
}
int dfs(int u,int lim)
{
	if(u==t) return lim;
	int flow=0;
	for(int i=cur[u];i;i=e[i].last)
	{
	    cur[u]=i; 
		int v=e[i].to;
		int w=e[i].c;
		if(w&&d[v]==d[u]+1)
		{
			int f=dfs(v,min(w,lim-flow));
			e[i].c-=f;
			e[i^1].c+=f;
			flow+=f;
			if(!f) d[v]=-1;
		}
	}
	return flow;
}
int dinic()
{
	int maxflow=0;
	int flow=0;
	while(bfs())
		while(flow=dfs(s,inf))
			maxflow+=flow;
	return maxflow;
}
void print(int x)
{
	for(int i=head[x];i;i=e[i].last)
	{
		int v=e[i].to;
		if(e[i].c&&v<=n)
        {
			printf("%d ",v);
		}
	}
	cout<<endl;
}
int main()
{
	scanf("%d%d",&k,&n);
	s=n+k+1;
	t=n+k+2;
	//从1-n是题目标号,从n+1-k+n是试卷的标号
	cnt=1;
	for(int i=1;i<=k;i++)
	{
		scanf("%d",&type[i]);
		add(i+n,t,type[i]);
		add(t,i+n,0); 
		tol+=type[i];
	}
	for(int i=1;i<=n;i++)//盘点每个试题的类型 
	{
		add(s,i,1);
		add(i,s,0);
		int tim;
		scanf("%d",&tim);
		for(int j=1;j<=tim;j++)
		{
			int x;//类型
			scanf("%d",&x);
			add(i,x+n,1);
			add(x+n,i,0);
		}
	}
	if(dinic()==tol)
 	for(int i=1;i<=k;i++)
	{
		printf("%d: ",i);
		print(i+n);
	}
	else cout<<"No Solution!"<<endl;
	return 0;
}
2021/2/5 17:06
加载中...