nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial

转移自老blog

hdu6445

题意：
        Given a tournament, you need to determine the direction of the remaining sides to maximize the answer. The answer is calculated in the following way. The vertices are labeled from 0 to n−1, and the matrix s is used to represent the edges.
        给你一个竞赛图，你需要确定某些剩余的边的方向，来最大化答案，答案通过下面的算法得到，点从0到n-1,s[i][j]是边
        输入文件s[i][j]=1代表i->j,s[i][j]=0代表j->i,s[i][j]=2代表方向未知

        化简分析,先加一个A(n,4) 然后减去对答案没有贡献以及负贡献，考虑对答案没有贡献的四元组,此四元组中存在且只存在一个点有两条边 从他出发，对答案贡献-1的点，存在恰好两个点，分别有两条边从他们出发。
        化最后发现只和点的出度的平方或者说(C(deg[i],2)) 因为sum(deg[i])为定值有关
        化最后可以用费用流做

#include<bits/stdc++.h>
using namespace std;


struct MCMF{
    static const int maxn=200+2+200*200,maxm=maxn*5;
    struct star{int v,nex;int c,w;} edge[maxm<<1];
    int head[maxn],cnt,n;
    int inq[maxn],pre[maxn];
    int dist[maxn];

    void ini(int n){
        cnt=-1;this->n=n;
        for(int i=0;i<=n;i++) head[i]=-1;
    }
    void add_edge(int u, int v, int c, int w){
        // cout<<"     "<<u<<" "<<v<<" "<<c<<" "<<w<<endl;
        edge[++cnt]=star{v,head[u],c, w}; head[u]=cnt;
        edge[++cnt]=star{u,head[v],0,-w}; head[v]=cnt;
    }
    void minCostMaxFlow(int s, int t,int&flow,int&cost){
        flow=cost=0;
        while(true){
            for(int i=0;i<=n;i++) dist[i]=1e9;
            queue<int>que; que.push(s);
            inq[s]=1; dist[s]=0;

            while(!que.empty()){
                int u=que.front();
                que.pop(); inq[u]=0;
                for(int i=head[u];~i;i=edge[i].nex){
                    int v=edge[i].v;
                    int c=edge[i].c,w=edge[i].w;
                    // if(c>eps&&dist[v]>dist[u]+w+eps){
                    if(c>0&&dist[v]>dist[u]+w){
                        dist[v]=dist[u]+w;
                        pre[v]=i;
                        if(!inq[v]) que.push(v);
                        inq[v]=1;
                    }
                }
            }
            if(dist[t]==1e9) return ;
            int addf=1e9;
            for(int x=t;x!=s;x=edge[pre[x]^1].v) addf=min(addf,edge[pre[x]].c);
            for(int x=t;x!=s;x=edge[pre[x]^1].v){
                edge[pre[x]].c-=addf;
                edge[pre[x]^1].c+=addf;
            }
            flow+=addf;
            cost+=dist[t]*addf;
        }
    }
} g;


/*
    ans=A(n,4)-sum(  C(2,deg[i])  )*8*(n-3)
*/

char graph[205][205];
int deg[205];

int main(){
    int T; scanf("%d",&T);
    while(T--){
        int n; scanf("%d",&n);
        for(int i=1;i<=n;i++) deg[i]=0;
        for(int i=1;i<=n;i++) scanf("%s",graph[i]+1);


        int tot=n;
        int s=++tot;
        int t=++tot;
        for(int i=1;i<=n;i++) {
            for(int j=i+1;j<=n;j++){
                if(graph[i][j]=='1') deg[i]++;
                else if(graph[i][j]=='0') deg[j]++;
            }
        }
        int ans=0;
        for(int i=1;i<=n;i++) ans+=deg[i]*(deg[i]-1)/2;

        g.ini(n+2+n*(n-1)/2);
        for(int i=1;i<=n;i++) {
            for(int j=i+1;j<=n;j++){
                if(graph[i][j]=='2'){
                    g.add_edge(s,++tot,1,0);
                    g.add_edge(tot,i,1,0);
                    g.add_edge(tot,j,1,0);
                    g.add_edge(i,t,1,deg[i]);//C(n+1,2)-C(n,2)=n
                    g.add_edge(j,t,1,deg[j]);
                    deg[i]++;
                    deg[j]++;
                }
            }
        }
        int cost,flow;
        g.minCostMaxFlow(s,t,cost,flow);
        printf("%d\n", n*(n-1)*(n-2)*(n-3)-(ans+flow)*8*(n-3));

    }
}