首页 > 代码库 > BZOJ 2597 WC2007 剪刀石头布 费用流
BZOJ 2597 WC2007 剪刀石头布 费用流
题目大意:给定一个竞赛图,一些边没有指定方向,求一个指定方向的方案使竞赛图中三元环的数量最多
直接做不好做,我们考虑补集法
三个点之间如果不是三元环,那么一定有一个点有两条出边
于是我们可以得到ans=C(n,3)-ΣC(degree[x],2)
于是我们考虑费用流的模型
每条边化为一个点
从源点向每个点连n-1条边,流量为1,费用为0,1,...,n-2
一条边如果可以或必须成为一个点的出边 那么就从这个点出发向这条边连一条流量为1,费用为零的边
每条边向汇点连一条流量为1,费用为零的边
跑最小费用最大流即可
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #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<cost[table[i].to] ) { cost[table[i].to]=cost[x]+table[i].cost; f[table[i].to]=min(f[x],table[i].f); from[table[i].to]=i; if(!v[table[i].to]) v[table[i].to]=1,q[++r]=table[i].to; } } if(!f[T]) return false; ans-=cost[T]*f[T]; for(i=from[T];i;i=from[table[i^1].to]) table[i].f-=f[T],table[i^1].f+=f[T]; return true; } int main() { //freopen("hand.in","r",stdin); //freopen("hand.out","w",stdout); int i,j; cin>>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<i;j++) { Link(++cnt,T,1,0); if(map[i][j]==0||map[i][j]==2) Link(i,cnt,1,0),edge[j][i]=tot-1; if(map[i][j]==1||map[i][j]==2) Link(j,cnt,1,0),edge[i][j]=tot-1; } ans=n*(n-1)*(n-2)/6; while( Edmons_Karp() ); cout<<ans<<endl; for(i=1;i<=n;i++) for(j=1;j<=n;j++) { if(i==j) printf("0%c",j==n?'\n':' '); else printf("%d%c",!edge[i][j]||table[edge[i][j]].f?0:1,j==n?'\n':' '); } return 0; } /* S 0 每个点变为图上的一个点 1~n 每条边变为图上的一个点 n+1~n+(n*(n-1)/2) T 10999 S向每个点连n-1条边 流量为1 费用为0~n-2 每条边变成的点向T连边 流量为1 费用为0 每个点向所有出边化为的点连边 流量为1 费用为0 跑费用流即可 每个点向所连边 */
BZOJ 2597 WC2007 剪刀石头布 费用流
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。