Bakser's Blog

我是逗比。

两道费用流神构图

| Comments

bzoj1449
首先进行一步神奇的转化
每场比赛都看作两队都输,然后通过费用流来判断使哪一队赢。
把球队和比赛都建成点。
从源点向每场比赛连一条流量为1,费用为0的边,代表只有一个球队可以赢。
每场比赛向两支连一条流量为1,费用为0的边,代表只能赢一次。
因为首先看作每场比赛都输了,所以此时赢一场就是多赢了一场,对答案影响:

是凸费用,对于赢了第i场的费用应该从i-1转移而来,而一开始应该是x=win[i],y=lose[i]+i进行的比赛场数。
从每个球队向汇点连费用如上的边。

bzoj1449
#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
#define N 5010
#define M 1010
#define INF 0x7f7f7f7f
#define MIN(a,b) (((a)<(b))?(a):(b))
typedef unsigned long long LL;
int n,m,win[N],lose[N],c[N],d[N],s,t,point[N+M],p[N+M],deg[N],dis[N+M];
LL ans;
bool in[N+M];
struct hh
{
    int u,v,next,cap,cost;
}edges[600000];
inline void addedge(int u,int v,int cap,int cost)
{
    static int en(-1);
    edges[++en].next=point[u];edges[en].u=u;edges[en].v=v;
    edges[en].cap=cap;edges[en].cost=cost;point[u]=en;
    if(cap)addedge(v,u,0,-cost);
}
inline bool spfa()
{
    static queue<int> q;
    memset(dis,0x7f,sizeof(dis));
    memset(in,0,sizeof(in));
    dis[s]=0;in[s]=1;
    q.push(s);
    while(!q.empty())
    {
        int u(q.front());q.pop();in[u]=0;
        for(int i=point[u];i!=-1;i=edges[i].next)
        if(edges[i].cap&&dis[edges[i].v]>dis[u]+edges[i].cost){
            dis[edges[i].v]=dis[u]+edges[i].cost;
            p[edges[i].v]=i;
            if(!in[edges[i].v])q.push(edges[i].v),in[edges[i].v]=1;
        }
    }
    return dis[t]<INF;
}
inline LL augment()
{
    int flow=INF;
    for(int x(t);x!=s;x=edges[p[x]].u)
        flow=MIN(flow,edges[p[x]].cap);
    for(int x(t);x!=s;x=edges[p[x]].u)
        edges[p[x]].cap-=flow,edges[p[x]^1].cap+=flow;
    return LL(flow)*LL(dis[t]);
}
int main()
{
    scanf("%d%d",&n,&m);
    s=0;t=n+m+1;
    memset(point,0xff,sizeof(point));
    for(int i=1;i<=n;i++)
        scanf("%d%d%d%d",win+i,lose+i,c+i,d+i);
    for(int i=1,a,b;i<=m;i++)
    {
        addedge(s,n+i,1,0);
        scanf("%d%d",&a,&b);
        addedge(n+i,a,1,0);
        addedge(n+i,b,1,0);
        deg[a]++;deg[b]++;
    }
    for(int i=1;i<=n;i++)
    {
        int x(win[i]),y(lose[i]+deg[i]);
        ans+=c[i]*x*x+d[i]*y*y;
        for(int j=1;j<=deg[i];j++)
            addedge(i,t,1,2*c[i]*x-2*d[i]*y+c[i]+d[i]),x++,y--;
    }
    while(spfa())
        ans+=augment();
    printf("%llu\n",ans);
    return 0;
}

此题每一步转化都十分的神。
首先运用补集转化思想,统计所有长度为三的环的个数相当于n个点中任选三个的方案数减去他们不能形成环的方案数。
不能形成环则这三个点的诱导子图中定有一个点的入度为2,所以答案为:

展开:

化简

而其中sigma(deg[i])是个定值,即边数n*(n-1)/2.
所以我们要做的就是确定每个点的入度,这可以用网络流解决
建图与上一题类似,每个点与汇点连边同样是凸费用的。

bzoj2597
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
typedef long double LD;
#define N 20000
#define INF 0x7f7f7f7f
#define MIN(a,b) (((a)<(b))?(a):(b))
struct hh
{
    int next,u,v,cap,cost;
}edges[600000];
int point[N],map[110][110],n,p[N],s,t,deg[N],cnt[N],hh[N][2],tot,dis[N];
LD ans,temp;
bool in[N];
inline void addedge(int u,int v,int cap,int cost)
{
    static int en(-1);
    edges[++en].next=point[u];edges[en].u=u;edges[en].v=v;
    edges[en].cap=cap;edges[en].cost=cost;point[u]=en;
    if(cap)addedge(v,u,0,-cost);
}
inline bool spfa()
{
    static queue<int> q;
    memset(dis,0x7f,sizeof(dis));
    memset(in,0,sizeof(in));
    dis[s]=0;in[s]=1;
    q.push(s);
    while(!q.empty())
    {
        int u(q.front());q.pop();in[u]=0;
        for(int i=point[u];i!=-1;i=edges[i].next)
        if(edges[i].cap&&dis[edges[i].v]>dis[u]+edges[i].cost){
            dis[edges[i].v]=dis[u]+edges[i].cost;
            p[edges[i].v]=i;
            if(!in[edges[i].v])q.push(edges[i].v),in[edges[i].v]=1;
        }
    }
    return dis[t]<INF;
}
inline LD augment()
{
    int flow=INF;
    for(int x(t);x!=s;x=edges[p[x]].u)
        flow=MIN(flow,edges[p[x]].cap);
    for(int x(t);x!=s;x=edges[p[x]].u)
        edges[p[x]].cap-=flow,edges[p[x]^1].cap+=flow;
    return LD(flow)*LD(dis[t]);
}
int main()
{
    scanf("%d",&n);
    memset(point,0xff,sizeof(point));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            scanf("%d",&map[i][j]);
            if(j>=i)continue;
            if(map[i][j]==1)deg[i]++;
            else if(map[i][j]==0)deg[j]++;
            else hh[++tot][0]=i,hh[tot][1]=j;
        }
    s=0;t=n+tot+1;
    ans+=LD(n*(n-1)*(n-2)/6.0)+LD(n*(n-1))/4.0;
    for(int i=1;i<=tot;i++)
    {
        addedge(s,n+i,1,0);
        addedge(n+i,hh[i][0],1,0),cnt[hh[i][0]]++;
        addedge(n+i,hh[i][1],1,0),cnt[hh[i][1]]++;
    }
    for(int i=1;i<=n;i++)
    {
        temp+=LD(deg[i]*deg[i]);
        int x(deg[i]);
        for(int j=1;j<=cnt[i];j++)
            addedge(i,t,1,2*x+1),x++;
    }
    while(spfa())
        temp+=augment();
    ans-=(temp/2.0);
    printf("%.0lf\n",(double)ans);
    for(int i=n+1;i<=n+tot;i++)
    {
        int win(0),lose(0);
        for(int j(point[i]);j!=-1&!win;j=edges[j].next)
            if(!edges[j].cap)
                    win=edges[j].v;
        lose=hh[i-n][win!=hh[i-n][1]];
        map[win][lose]=1;map[lose][win]=0;
    }
    for(int i=1;i<=n;i++,puts(""))
        for(int j=1;j<=n;j++)
        {
            printf("%d",map[i][j]);
            if(j!=n)putchar(' ');
        }
    return 0;
}

Comments

comments powered by Disqus