大家好，又见面了，我是你们的朋友全栈君。
比较有思维含量的一道题
题意：给混合完全图定向（定向为竞赛图）使得有最多的三元环
三元环条件要求比较高，还不容易分开处理。
正难则反
考虑，什么情况下，三元组不是三元环
一定是一个点有2个入度，一个点有2个出度，另一个点一个入度，一个出度
也就是说，每存在一个>=2入度的点，那么会减少一些三元环
进而考虑，如果一个点有d个入度，那么减少的三元环其实是：C(d,2)，即，包括它自己，再包括任意两个指向它的点（这里，a指向b，代表a能赢b），构成的三元组都不是三元环
考虑每个点作为某些个非法三元组的话，那么，
总共的三元环是：C(n,3)-∑C(du[i],2)
C(du[i],2)统计了所有与i有关的非法三元组，所以不重不漏统计完了。
怎样最小化这个∑？
定向，就是某些点的入度增加的过程。所以考虑某个点增加一个入度，减少的三元环的数量是多少。
即C(d+1,2)-C(d,2)=d即减少原来度数的三元环
这个减少是逐一增加的，n*(n-1)/2是下凸函数，可以考虑拆边费用流。
这个题的具体做法是：
把每个要定向的边看做一个点，从S到这个点连(1,0)，意义是只能确定一个方向
这个点向所代表的边的两个原图端点连(1,0)的边，意义是增加入度，且只能给一个增加
每个原图 节点向T连(1,d),(1,d+1)…(1,d+n-2)的边，意义是，每增加一个入度，就会增加d的代价
最小费用最大流，spfa恰好先选择d，再选择d+1，，，，刚好符合实际的代价
最大流之后，每个边都定向完毕，而且增加的代价也都是对的。
至于输出方案，找每个边的代表点，看其哪一侧流量是0，就是哪一侧输。
代码：
#include<bits/stdc++.h> #define il inline #define reg register int #define numb (ch^'0') using namespace std; typedef long long ll; il void rd(int &x){ char ch;bool fl=false; while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true); for(x=numb;isdigit(ch=getchar());x=x*10+numb); (fl==true)&&(x=-x); } namespace Miracle{ const int N=105; const int inf=0x3f3f3f3f; int n,s,m,t; struct node{ int nxt,to,w,v; }e[2*(N*N+N*N*2+N*N)]; int hd[N+N*N],cnt=1; void add(int x,int y,int w,int v){ e[++cnt].nxt=hd[x]; e[cnt].to=y; e[cnt].v=v; e[cnt].w=w; hd[x]=cnt; e[++cnt].nxt=hd[y]; e[cnt].to=x; e[cnt].w=0; e[cnt].v=-v; hd[y]=cnt; } int mp[N][N]; int op[N][N]; queue<int>q; bool vis[N+N*N]; int dis[N*N+N]; int incf[N*N+N],pre[N*N+N]; bool spfa(){ while(!q.empty()) q.pop(); memset(dis,inf,sizeof dis); dis[s]=0; q.push(s); pre[s]=0; incf[s]=inf; while(!q.empty()){ int x=q.front();q.pop(); vis[x]=0; for(reg i=hd[x];i;i=e[i].nxt){ int y=e[i].to; if(e[i].w){ if(dis[y]>dis[x]+e[i].v){ dis[y]=dis[x]+e[i].v; pre[y]=i; incf[y]=min(incf[x],e[i].w); if(!vis[y]){ vis[y]=1; q.push(y); } } } } } if(dis[t]==inf) return false; return true; } int cos,maxflow; int du[N]; void upda(){ int x=t; while(pre[x]){ e[pre[x]].w-=incf[t]; e[pre[x]^1].w+=incf[t]; x=e[pre[x]^1].to; } cos+=incf[t]*dis[t]; maxflow+=incf[t]; } int num(int i,int j){ return n+(i-1)*(n-1)+j; } int main(){ rd(n); s=0,t=n+n*n+1; for(reg i=1;i<=n;++i){ for(reg j=1;j<=n;++j){ rd(mp[i][j]); if(mp[i][j]==2&&i<j){ add(s,num(i,j),1,0); add(num(i,j),i,1,0); add(num(i,j),j,1,0); }else if(mp[i][j]==1){ du[j]++; } } } int ans=n*(n-1)*(n-2)/6; for(reg i=1;i<=n;++i){ ans-=du[i]*(du[i]-1)/2; for(reg j=du[i];j<=n-2;++j){ add(i,t,1,j); } } while(spfa()) upda(); ans-=cos; printf("%d\n",ans); memcpy(op,mp,sizeof mp); for(reg i=1;i<=n;++i){ for(reg j=1;j<=n;++j){ if(mp[i][j]==2&&i<j){ int x=num(i,j); for(reg p=hd[x];p;p=e[p].nxt){ int y=e[p].to; if(y!=s&&e[p].w==0){ if(y==j){ op[i][j]=1; op[j][i]=0; }else{ op[i][j]=0; op[j][i]=1; } } } } } } for(reg i=1;i<=n;++i){ for(reg j=1;j<=n;++j){ printf("%d ",op[i][j]); }puts(""); } return 0; } } signed main(){ Miracle::main(); return 0; } /* Author: *Miracle* Date: 2018/12/15 11:01:16 */
总结：
值得学习的是：
1.正难则反，考虑非法的三元组，这样可以通过度数直接分开计算
2.边点转化，对无向图定向、而且贡献和点的入度有关，可以尝试采取这种策略。
3.下凸函数拆边费用流。因为下凸函数，所以最小费用的时候，每次会先选择最小的，然后往右或者往左选，那么拆边，实际上真正选择的恰好也符合实际情况。
转载于:https://www.cnblogs.com/Miracevin/p/10122842.html
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/107141.html原文链接：https://javaforall.net
