【BZOJ4155】[Ipsc2015]Humble Captains

2016.03.19 08:49 Sat | 38次阅读 | 旧日oi | 固定链接 | 源码

题解

最小割+背包

第一问直接建最大权闭合图的模型搞就行了。
第二问可以把每个点的权值看成是这个点的度数,那么我们就是要把点权分成两组,使得两组的点权之和差最小。
这个东西跑一个压位的背包就可以了。
单组复杂度大概n^3/32左右吧,网络流比较迷……

my code

#include <bits/stdc++.h>
using namespace std;
#define N 205
#define inf 0x3f3f3f3f
int n,m,T;
int h[N],tp=1;
struct edge{int to,next,val;}e[2000000];
void ae(int u,int v,int w=0){e[++tp].to=v;e[tp].next=h[u];e[tp].val=w;h[u]=tp;}
struct MAXFLOW
{
    int S,T,dis[N],q[N],f,t;
    void init(int s,int t){S=s;T=t;memset(h,0,sizeof(h));tp=1;} 
    void add(int u,int v,int w){ae(u,v,w);ae(v,u,0);}
    int bfs(){
        memset(dis,0,sizeof(dis));dis[S]=1;q[f=t=1]=S;
        while(f<=t){
            int u=q[f++];
            for(int v,i=h[u];i;i=e[i].next) 
            if(e[i].val&&!dis[v=e[i].to]) dis[q[++t]=v]=dis[u]+1;
        }
        return dis[T];
    }
    int dfs(int u,int l)
    {
        if(u==T) return l;
        int c=0,t;
        for(int v,i=h[u];i;i=e[i].next)
        if(e[i].val&&dis[v=e[i].to]==dis[u]+1)
        {
            t=dfs(v,min(l-c,e[i].val));
            if(t){e[i].val-=t;e[i^1].val+=t;if((c+=t)==l) break;}
            else dis[v]=-1;
        }
        return c;
    }
    int dinic(){int ret=0;while(bfs()) ret+=dfs(S,inf);return ret;}
}g;
int w[205];
bitset<20000>f;
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("tt.in","r",stdin);
    #endif
    for(cin>>T;T--;)
    {
        scanf("%d%d",&n,&m);
        memset(w,0,sizeof(w));
        g.init(1,2);
        for(int u,v,i=1;i<=m;i++)
        {
            scanf("%d%d",&u,&v);
            w[u]++;w[v]++;
            if(u>v) swap(u,v);
            if(u==1) g.add(u,v,1);
            else if(u==2) g.add(v,u,1);
            else 
            {
                g.add(v,u,1);
                g.add(u,v,1);
            }
        }
        printf("%d ",m-g.dinic());
        f=1;int ans=inf;
        for(int i=3;i<=n;i++) f|=f<<w[i];
        for(int i=0;i<=m;i++) 
        if(f[i])ans=min(ans,abs(w[1]+i-m));
        printf("%d\n",ans);
    }
}