# 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 inq[maxn],pre[maxn];
int dist[maxn];

void ini(int n){
cnt=-1;this->n=n;
}
void add_edge(int u, int v, int c, int w){
// cout<<"     "<<u<<" "<<v<<" "<<c<<" "<<w<<endl;
}
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;
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 ;
for(int x=t;x!=s;x=edge[pre[x]^1].v){
}
}
}
} 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'){
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));

}
}
```

目录