正解:网络流

解题报告:

题目大意其实就说有一个$n$个节点的有向完全图,然后部分边的方向已经给定了,要求确定所有边的方向使三元环数目有$max$.这里三元环的定义是说三条边的方向一致,即同为顺逆时针$QwQ$

话说这种三元环问题通常就是考虑点的度数?考虑下如果是非三元环一定是有一个入度为2的点,考虑枚举这种点,那就有$as=\binom{n}{3}-\sum\binom{in_i}{2}=\frac{n(n-1)(n-2)}{6}-\sum\frac{in_i^2-in_i}{2}=\frac{n(n-1)(n-2)}{6}+\frac{n(n-1)}{2}-\sum\frac{in_i^2}{2}$,所以现在就是要最小化这个,$\sum\frac{in_i^2}{2}$

这时候要用到费用递增$QwQ$,因为之前都没安利过这个姿势的样子所以大概港下,,,也不会很详细港的因为懒$bushi$

就对于某条边,若费用是关于流量的一个函数,且满足斜率单调增,可以考虑拆边,第$x$条边就$f_{x}-f_{x-1}$,然后就欧克克辣$QwQ$

所以这里一样的嘛,由前面得$f(x)=x^2$显然递增,所以像前面说的那样拆边就好$QwQ$

欧克最后总结下怎么建图$QwQ$?考虑建一排点表示未定向的边,再建一排点表示所有点,于是就$S$向边连流量为1费用为0的边,边向端点连流量为1费用为0的边,各点向$T$连边如上方法

然后就做完辣?

$QwQ$

#include<bits/stdc++.h>

using namespace std;

#define il inline

#define gc getchar()

#define t(i) edge[i].to

#define w(i) edge[i].wei

#define fy(i) edge[i].fy

#define ri register int

#define rb register bool

#define rc register char

#define rp(i,x,y) for(ri i=x;i<=y;++i)

#define e(i,x) for(ri i=head[x];~i;i=edge[i].nxt)

const int N=1e4+;

int head[N],ed_cnt=-,vis[N],S,T,fr_ed[N],fr_nod[N],dis[N],g[N][N],du[N],num[N],nod_cnt,n,as;

struct ed{int to,nxt,wei,fy;}edge[N<<];

struct node{int x,y;}nod[N];

il int read()

{

    rc ch=gc;ri x=;rb y=;

    while(ch!='-' && (ch>'' || ch<''))ch=gc;

    if(ch=='-')ch=gc,y=;

    while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=gc;

    return y?x:-x;

}

il void ad(ri x,ri y,ri z,ri p)

{edge[++ed_cnt]=(ed){x,head[y],z,p};head[y]=ed_cnt;edge[++ed_cnt]=(ed){y,head[x],,p};head[x]=ed_cnt;}

il bool spfa()

{

    queue<int>Q;Q.push(S);memset(vis,,sizeof(vis));vis[S]=;memset(dis,,sizeof(dis));dis[S]=;

    while(!Q.empty())

    {

        ri nw=Q.front();Q.pop();vis[nw]=;

        e(i,nw)

            if(w(i) && fy(i)+dis[nw]<dis[t(i)])

            {dis[t(i)]=dis[nw]+fy(i),fr_ed[t(i)]=i,fr_nod[t(i)]=nw;if(!vis[t(i)])Q.push(t(i)),vis[t(i)]=;}

    }

    if(dis[T]==dis[])return ;

    ri flow=dis[T+];

    for(ri i=T;i!=S;i=fr_nod[i])flow=min(flow,w(fr_ed[i]));

    for(ri i=T;i!=S;i=fr_nod[i])w(fr_ed[i])-=flow,w(fr_ed[i]^)+=flow;as+=dis[T]*flow;

    return ;

}

int main()

{

    memset(head,-,sizeof(head));n=read();S=n+,T=nod_cnt=n+;

    rp(i,,n)

    {

        rp(j,,n)

        {

            g[i][j]=read();

            if(g[i][j]== && i<j)

            {nod[++nod_cnt]=(node){i,j};ad(nod_cnt,S,,);ad(i,nod_cnt,,);ad(j,nod_cnt,,);++num[i];++num[j];}

            else du[i]+=g[i][j];

        }

    }

    rp(i,,n){as+=du[i]*du[i];rp(j,,num[i])ad(i,T,,*(du[i]+j)-);}

    while(spfa());

    printf("%d\n",n*(n-)*(n-)/-(as-n*(n-)/)/);

    rp(i,n+,nod_cnt)

    {

        ri tmp;e(j,i)if(t(j)!=S && !w(j)){tmp=t(j);break;}

        if(tmp==nod[i].x)g[nod[i].x][nod[i].y]=,g[nod[i].y][nod[i].x]=;

        else g[nod[i].x][nod[i].y]=,g[nod[i].y][nod[i].x]=;

    }

    rp(i,,n){rp(j,,n)printf("%d ",g[i][j]);printf("\n");}

    return ;

}

没写完,不想写了$kk$,先存着$kk$

巴特西

洛谷$P4249\ [WC2007]$剪刀石头布网络流

正解:网络流

解题报告:

最新文章

热门文章

巴特西

洛谷$P4249\ [WC2007]$剪刀石头布 网络流

正解:网络流

解题报告:

最新文章

热门文章

洛谷$P4249\ [WC2007]$剪刀石头布网络流