首页 > 代码库 > 【BZOJ2597】【Wc2007】剪刀石头布 费用流,没写zkw卡时过
【BZOJ2597】【Wc2007】剪刀石头布 费用流,没写zkw卡时过
题解,比较常规式是费用流,没写那个神贪心。
首先是三元环需要取补集,先C(n,3)算出总环数,然后减去失败的三元环。
我们发现在一个三元环中,如果有某个选手入度(or 出度)为2,那么就会破坏这个环。
所以当选手有x个度时,就会破坏∑(i∈[0,x])个三元环(0+....+x-1),P.S.这个是C(x,2)推出来的。
建图:
第一层源点
到下一层每个点若干条边
条数: 那个选手可能赢的次数,
费用: 第i条边费用i-1,
流量: 1
第二层选手
到可能赢的每个对应竞赛建边
条数: 1
费用: 0
流量: 1
第三层比赛
到汇点连边
条数: 1
费用: 0
流量: 1
第四层汇点
完事。
除了1、2层中间的多建边有点思想成分,其它都很渣。
不多说。
至于那个方案数,就是check2、3层间边的满流和对应。
呃,来个图告诉一下大家zkw费用流和裸费用流的差距。
zkw费用流是wyfcyx写的。
然后popoqqq和eolv写的也是费用流,……连小常数君eolv都16s……醉了啊!!!
他当前博客http://wyfcyx.is-programmer.com/
代码:
#include <queue> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define N 5500 #define M 50000 #define P 105 #define inf 0x3f3f3f3f using namespace std; struct KSD { int u,v,len,fee,next; }e[M]; int head[N],cnt; void add(int u,int v,int w,int len) { cnt++; e[cnt].u=u; e[cnt].v=v; e[cnt].len=len; e[cnt].fee=w; e[cnt].next=head[u]; head[u]=cnt; } int s,t,dist[N]; int pre[N],lim[N]; bool in[N]; queue<int>q; int spfa() { memset(dist,0x3f,sizeof(dist)); while(!q.empty())q.pop(); int i,u,v; dist[s]=0,in[s]=1; lim[s]=inf; q.push(s); while(!q.empty()) { u=q.front(),q.pop(),in[u]=0; for(i=head[u];i;i=e[i].next) { v=e[i].v; if(!e[i].len)continue; if(dist[v]>dist[u]+e[i].fee) { dist[v]=dist[u]+e[i].fee; lim[v]=min(e[i].len,lim[u]); pre[v]=i; if(!in[v]) { in[v]=1; q.push(v); } } } } return dist[t]; } void handle(int flow) { for(int i=pre[t];i;i=pre[e[i].u]) { e[i].len-=flow; e[i^1].len+=flow; } } int map[P][P],ans[P][P],minfee; int n,m,sum[P],id[P][P],idx[N],idy[N]; int win[P]; int main() { // freopen("hand.in","r",stdin); // freopen("hand.out","w",stdout); cnt=1; int i,j,k,cnt,v; scanf("%d",&n); m=n*(n-1)/2,minfee=n*(n-1)*(n-2)/6; s=n+m+1,t=n+m+2,cnt=n; for(i=1;i<=n;i++)for(j=i+1;j<=n;j++)id[i][j]=++cnt,idx[cnt]=i,idy[cnt]=j,add(cnt,t,0,1),add(t,cnt,0,0); 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=i+1;j<=n;j++) { if(map[i][j])add(i,id[i][j],0,1),add(id[i][j],i,0,0),win[i]++; if(map[i][j]-1)add(j,id[i][j],0,1),add(id[i][j],j,0,0),win[j]++; } for(i=1;i<=n;i++)for(j=1;j<=win[i];j++)add(s,i,j-1,1),add(i,s,1-j,0); while(spfa(),dist[t]<inf) { minfee-=dist[t]*lim[t]; handle(lim[t]); } printf("%d\n",minfee); for(k=n+1;k<s;k++) { for(i=head[k];i;i=e[i].next) { v=e[i].v; if(v!=t&&e[i].len) { if(v==idx[k])ans[idx[k]][idy[k]]=1,ans[idy[k]][idx[k]]=0; else ans[idx[k]][idy[k]]=0,ans[idy[k]][idx[k]]=1; } } } for(i=1;i<=n;i++) { for(j=1;j<n;j++)printf("%d ",ans[i][j]); printf("%d\n",ans[i][n]); } return 0; }
【BZOJ2597】【Wc2007】剪刀石头布 费用流,没写zkw卡时过
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。