BZOJ 2597 WC2007 剪刀石头布 费用流

题目大意：给定一个竞赛图，一些边没有指定方向，求一个指定方向的方案使竞赛图中三元环的数量最多

直接做不好做，我们考虑补集法

三个点之间如果不是三元环，那么一定有一个点有两条出边

于是我们可以得到ans=C(n,3)-ΣC(degree[x],2)

于是我们考虑费用流的模型

每条边化为一个点

从源点向每个点连n-1条边，流量为1，费用为0,1,...,n-2

一条边如果可以或必须成为一个点的出边 那么就从这个点出发向这条边连一条流量为1，费用为零的边

每条边向汇点连一条流量为1，费用为零的边

跑最小费用最大流即可

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #define M 11000 #define S 0 #define T 10999 #define INF 0x3f3f3f3f using namespace std; struct abcd{ int to,f,cost,next; }table[1001001]; int head[M],tot=1; int n,cnt,ans,map[110][110],edge[110][110]; void Add(int x,int y,int f,int cost) { table[++tot].to=y; table[tot].f=f; table[tot].cost=cost; table[tot].next=head[x]; head[x]=tot; } void Link(int x,int y,int f,int cost) { Add(x,y,f,cost); Add(y,x,0,-cost); } bool Edmons_Karp() { static int q[65540],f[M],from[M],cost[M]; static unsigned short r,h; static bool v[M]; int i; memset(cost,0x3f,sizeof cost); q[++r]=S;f[S]=INF;cost[S]=0;f[T]=0; while(r!=h) { int x=q[++h];v[x]=0; for(i=head[x];i;i=table[i].next) if( table[i].f && cost[x]+table[i].cost
      
       >n;cnt=n; for(i=1;i<=n;i++) for(j=1;j<=n;j++) scanf("%d",&map[i][j]); for(i=1;i<=n;i++) for(j=0;j<=n-2;j++) Link(S,i,1,j); for(i=1;i<=n;i++) for(j=1;j