MnZn求助除了样例全WA
查看原帖
MnZn求助除了样例全WA
341373
Autofreeze楼主2021/2/24 15:46
#include<bits/stdc++.h>
#define N 2001001
#define MAX 2001
#define re register
#define inf 1e18
using namespace std;
typedef long long ll;
typedef double db;
inline void read(re ll &ret)
{
	ret=0;re char c=getchar();re bool pd=false;
	while(!isdigit(c)){pd|=c=='-';c=getchar();}
	while(isdigit(c)){ret=(ret<<1)+(ret<<3)+(c&15);c=getchar();}
	ret=pd?-ret:ret;
	return;
}
ll m,n,p[N],head[N],s,t,cnt=-1,sum,now[N],dep[N];
char tools[N];
struct edge
{
	ll from,to,dis,nxt;
}e[N];
inline void add(re ll u,re ll v,re ll d)
{
	e[++cnt].from=u;
	e[cnt].to=v;
	e[cnt].dis=d;
	e[cnt].nxt=head[u];
	head[u]=cnt;
	return;
}
queue<ll>q;
inline bool bfs()
{
	memset(dep,0,(t+1)*sizeof(ll));
	dep[s]=1;
	q.push(s);
	while(!q.empty())
	{
		re ll ver=q.front();
		q.pop();
		now[ver]=head[ver];
		for(re int i=head[ver];i!=-1;i=e[i].nxt)
		{
			if(!dep[e[i].to]&&e[i].dis)
			{
				dep[e[i].to]=dep[ver]+1;
				q.push(e[i].to);
			}
		}
	}
	return dep[t];
}
inline ll dfs(re ll ver,re ll lim)
{
	if(ver==t)
		return lim;
	re ll out=0;
	for(re ll &i=now[ver];(~i)&&lim;i=e[i].nxt)
	{
		if(e[i].dis&&dep[e[i].to]==dep[ver]+1)
		{
			re ll tmp=dfs(e[i].to,min(lim,e[i].dis));
			lim-=tmp;
			out+=tmp;
			e[i].dis-=tmp;
			e[i^1].dis+=tmp;
		}
		if(!lim)
			break;
	}
	if(!out)
		dep[ver]=0;
	return out;
}
inline ll dinic(re ll s,re ll t)
{
	re ll ret=0;
	while(bfs())
		ret+=dfs(s,inf);
	return ret;
}
signed main()
{
	memset(head,-1,sizeof(head));
	read(m);
	read(n);
	t=m+n+1;
	memset(tools,0,sizeof(tools));
	for(re int i=1;i<=m;i++)
	{
		read(p[i]);
		sum+=p[i];
		add(s,i,p[i]);
		add(i,s,0);
		cin.getline(tools,10000);
		re ll ulen=0,tool;
		while(sscanf(tools+ulen,"%lld",&tool)==1)
		{
		    add(i,tool+m,inf);
		    add(tool+m,i,0);
		    if(!tool)
		        ulen++;
		    else
		        while(tool)
				{
		            tool/=10;
		            ulen++;
		        }
		    ulen++;
		}
	}
	for(re int i=m+1;i<=m+n;i++)
		read(p[i]),add(i,t,p[i]),add(t,i,0);
	re ll tmp=dinic(s,t);
	for(re int i=head[s];~i;i=e[i].nxt)
	{
		if(e[i].dis)
			printf("%lld ",e[i].to);
	}
	puts("");
	for(re int i=head[t];~i;i=e[i].nxt)
	{
		if(!e[i^1].dis)
			printf("%lld ",e[i].to-m);
	}
	puts("");
	printf("%lld\n",sum-tmp);
	exit(0);
}

2021/2/24 15:46
加载中...