真的不知道自己错哪儿了。。。
查看原帖
真的不知道自己错哪儿了。。。
68207
CreeperLordVader楼主2019/2/3 19:49

RT,WA了十几次了

还是不过

#include<bits/stdc++.h>
#define INF 0x7f
using namespace std;
struct edge
{
    int from,to,cap,flow;
};
struct edge2
{
    int to,w;
};
int n,s,t,deg[150];
int ans,cnt,d[150],cur[150],cnt2,tot;
int route[150];
bool vis[150],b;
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){from,to,cap,0});
    e.push_back((edge){to,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(unsigned 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)
{
    route[++tot]=x;
    bool ok=0;
    for(unsigned int i=0; i<v2[x].size(); i++)
    {
        edge2& ed2=e2[v2[x][i]];
        if(b)return ;
        if(ed2.w)
        {
        	ok=1;
            ed2.w--;
            print(ed2.to);
        }
    }
    if(!ok)
    {
    	deg[x]--;
    	b=1;
	}
}
int main()
{
    while(scanf("%d",&n)==1)
    {
        e.clear();
        e2.clear();
        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++)
        {
        	v[i].clear();
        	v2[i].clear();
		}
        for(int i=1; i<=n; i++)
        {
            int num;
            read(num);
            while(num--)
            {
                int x;
                read(x);
                deg[x]++;
                deg[i]--;
                link(i,x,INF);
            }
        }
        for(int i=1; i<=n; i++)
        {
            if(deg[i]<0)
            {
                link(i,t,-deg[i]);
                ans-=deg[i];
            }
            else if(deg[i]>0)link(s,i,deg[i]);
        }
        ans-=dinic();
        printf("%d\n",ans);
        for(int i=0; i<e.size(); i+=2)
        {
        	edge& ed=e[i];
            if(e[i].from==s||e[i].to==s||e[i].to==t||e[i].from==t)continue;
			link2(ed.from,ed.to,e[i].flow+1);
            deg[ed.from]-=ed.flow;
            deg[ed.to]+=ed.flow;
        }
        for(int i=1; i<=n; i++)
        {
            while(deg[i]<0)
            {
            	tot=b=0;
            	deg[i]++;
                print(i);
                printf("%d",route[1]);
                for(int j=2;j<=tot;j++)printf(" %d",route[j]);
				putchar('\n');
            }
        }
    }
}
2019/2/3 19:49
加载中...