蒟蒻求助,死活不过
查看原帖
蒟蒻求助,死活不过
68207
CreeperLordVader楼主2019/2/3 09:27

老是WA

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
struct edge
{
	int to,cap,flow;
};
struct edge2
{
	int to,w;
};
int n,s,t,deg[150],out[150],pa[150];
int ans,cnt,d[150],cur[150],cnt2;
bool vis[150];
vector<edge>e;
vector<edge2>e2;
vector<int>v[150];
vector<int>v2[150];
void read(int& x)
{
	char c=getchar();
	x=0;
	while(c<'0'||c>'9')c=getchar();
	while(c>='0'&&c<='9')
	{
		x=x*10+c-'0';
		c=getchar();
	}
}
void link(int from,int to,int cap)
{
	e.push_back((edge){to,cap,0});
	e.push_back((edge){from,0,0});
	cnt=e.size();
	v[from].push_back(cnt-2);
	v[to].push_back(cnt-1);
}
void link2(int from,int to,int w)
{
	e2.push_back((edge2){to,w});
	cnt2=e2.size();
	v2[from].push_back(cnt2-1);
}
bool bfs()
{
    queue<int>q;
    memset(vis,0,sizeof(vis));
    d[s]=0;
    vis[s]=1;
    q.push(s);
    while(!q.empty())
    {
        int fa=q.front();
        q.pop();
        for(int i=0;i<v[fa].size();i++)
        {
            edge& ed=e[v[fa][i]];
            if(!vis[ed.to]&&ed.cap>ed.flow)
            {
            	vis[ed.to]=1;
                d[ed.to]=d[fa]+1;
                q.push(ed.to);
            }
        }
    }
    return vis[t];
}
int dfs(int x,int a)
{
	if(x==t||!a)return a;
	int flow=0,f;
	for(int& i=cur[x];i<v[x].size();i++)
	{
		edge& ed=e[v[x][i]];
		if(d[ed.to]==d[x]+1&&(f=dfs(ed.to,min(a,ed.cap-ed.flow)))>0)
		{
			flow+=f;
			ed.flow+=f;
			e[v[x][i]^1].flow-=f;
			a-=f;
			if(!a)break;
		}
	}
	return flow;
}
int dinic()
{
	int maxflow=0;
	while(bfs())
	{
		memset(cur,0,sizeof(cur));
		maxflow+=dfs(s,INF);
	}
	return maxflow;
}
void print(int x,int num)
{
	if(num==1)printf("%d",x);
	else printf(" %d",x);
	for(int i=0;i<v2[x].size();i++)
	{
		edge2& ed2=e2[v2[x][i]];
		if(ed2.w)
		{
			out[x]--;
			pa[ed2.to]--;
			ed2.w--;
			print(ed2.to,num+1);
			break;
		}
	}
}
int main()
{
	while(scanf("%d",&n)==1)
	{
		e.clear();
		e2.clear();
		memset(out,0,sizeof(out));
		memset(pa,0,sizeof(pa));
		memset(deg,0,sizeof(deg));
		ans=0;
		s=0;
		t=n+1;
		v[s].clear();
		v[t].clear();
		v2[s].clear();
		v2[t].clear();
		for(int i=1;i<=n;i++)
		{
			int num;
			read(num);
			v[i].clear();
			v2[i].clear();
			while(num--)
			{
				int x;
				read(x);
				deg[x]++;
				deg[i]--;
				link(i,x,INF);
			}
		}      i x
		for(int i=1;i<=n;i++)
		{
			if(deg[i]<0)
			{
				link(i,t,-deg[i]);
				ans-=deg[i];
			}
			if(deg[i]>0)link(s,i,deg[i]);
		}
		ans-=dinic();
		printf("%d\n",ans);
		for(int i=1;i<=n;i++)
		{
			for(int j=0;j<v[i].size();j++)
			{
				edge ed=e[v[i][j]];
				if(ed.to!=s&&ed.to!=t&&ed.cap==INF&&ed.flow+1>0)
				{
					out[i]+=ed.flow+1;
					pa[ed.to]+=ed.flow+1;
					link2(i,ed.to,ed.flow+1);
				}
			}
		}
		int num=0;
		while(num<ans)
		{
			for(int i=1;i<=n;i++)
			{
				if(out[i]>pa[i])
				{
					print(i,1);
					putchar('\n');
					num++;
					break;
				}
			} 
		}
	}
}
2019/2/3 09:27
加载中...