bzoj2597: [Wc2007]剪刀石头布(费用流)
2024-09-29 13:12:16
不得不说这思路真是太妙了
考虑能构成三元组很难,那我们考虑不能构成三元组的情况是怎么样
就是说一个三元组$(a,b,c)$,其中$a$赢两场,$b$赢一场,$c$没有赢
所以如果第$i$个人赢了$w_i$场,那么总共的不能构成的三元组就是$\sum_i{w_i*(w_i-1)}{2}$
最大化满足的数量,就是最小化不满足的数量,就是最小化上面那个式子
那么我们考虑构建网络流
建源汇
对第$i$个人,从它向汇点连容量为$n$的边
对于每一对$i,j$之间的比赛建一个点$C_{i,j}$,如果这场比赛尚未进行,那么源点向$C_{i,j}$连容$1$费$0$的边,$C_{i,j}向$i$和$j$连容$1$费$0$的边,表示这场比赛只能改变一个点的赢的场数
我们要最小化上式,那么我们考虑在费用上做文章
每个点$i$向汇点连边,但因为费用的增加是一次比一次大的,所以我们考虑把这条边拆成$n$条边,容量为$1$费用分别为$0,1,2...$
因为费用流每一次都先增广最小的费用,所以只要求出最小费用最大流即可
//minamoto
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define inf 0x3f3f3f3f
using namespace std;
#define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[<<],*p1=buf,*p2=buf;
inline int read(){
#define num ch-'0'
char ch;bool flag=;int res;
while(!isdigit(ch=getc()))
(ch=='-')&&(flag=true);
for(res=num;isdigit(ch=getc());res=res*+num);
(flag)&&(res=-res);
#undef num
return res;
}
const int N=,M=;
int head[N],Next[M],ver[M],edge[M],cost[M],tot=;
inline void add(int u,int v,int e,int c=){
ver[++tot]=v,Next[tot]=head[u],head[u]=tot,edge[tot]=e,cost[tot]=c;
ver[++tot]=u,Next[tot]=head[v],head[v]=tot,edge[tot]=,cost[tot]=-c;
}
int dis[N],vis[N],cur[N],S,T,ans;
queue<int> q;
bool spfa(){
memset(dis,-,sizeof(dis));
memset(vis,,sizeof(vis));
memcpy(cur,head,sizeof(head));
q.push(T),dis[T]=,vis[T]=;
while(!q.empty()){
int u=q.front();q.pop(),vis[u]=;
for(int i=head[u];i;i=Next[i])
if(edge[i^]){
int v=ver[i],c=cost[i];
if(dis[v]<||dis[v]>dis[u]-c){
dis[v]=dis[u]-c;
if(!vis[v]) vis[v]=,q.push(v);
}
}
}
return ~dis[S];
}
int dfs(int u,int limit){
if(!limit||u==T) return limit;
int flow=,f;vis[u]=;
for(int i=cur[u];i;cur[u]=i=Next[i]){
int v=ver[i];
if(dis[v]==dis[u]-cost[i]&&!vis[v]&&(f=dfs(v,min(limit,edge[i])))){
flow+=f,limit-=f;
edge[i]-=f,edge[i^]+=f;
ans-=f*cost[i];
if(!limit) break;
}
}
vis[u]=;
return flow;
}
void zkw(){while(spfa()) dfs(S,inf);}
int mp[][],win[][],n,cnt;
int main(){
//freopen("testdata.in","r",stdin);
n=read();
for(int i=;i<=n;++i)
for(int j=;j<=n;++j)
mp[i][j]=read();
S=,cnt=n;
for(int i=;i<=n;++i)
for(int j=;j<i;++j){
add(S,++cnt,);
if(mp[i][j]==||mp[i][j]==) add(cnt,i,),win[j][i]=tot-;
if(mp[i][j]==||mp[i][j]==) add(cnt,j,),win[i][j]=tot-;
}
T=cnt+;
for(int i=;i<=n;++i)
for(int j=;j<n;++j)
add(i,T,,j);
ans=n*(n-)*(n-)/;
zkw();
printf("%d\n",ans);
for(int i=;i<=n;++i){
for(int j=;j<=n;++j)
printf("%s%d",j==?"":" ",!win[i][j]||edge[win[i][j]]?:);
putchar();
}
return ;
}
最新文章
- .stop()
- hdu2108(判断凸多边形)
- Android模拟器部署历程
- asp双表查询
- 函数lock_rec_get_nth_bit
- dd usb 启动盘制作 成功版本
- vim 折叠技巧
- hdu 2769 uva 12169 Disgruntled Judge 拓展欧几里德
- Luogu1574 超级数
- ok6410如何从sdram中启动uboot 调试 这是一个猜想还没有验证
- kali syn洪水攻击实例
- [Shell]Shell调用并获取执行jar包后的返回值
- HDMI接口的PCB设计
- laravel中类似于thinkPHP中trace功能
- spring StopWatch用法
- Hadoop生态圈-Flume的主流source源配置
- bzoj 2167: 公交车站
- 【Python之路】第二十三篇--Django【进阶篇】
- 关于Gateway
- JVM原理:4 运行期优化
热门文章
- STL list链表的用法详解
- django中使用多个数据库,跨库查询
- Python习题-统计日志中访问次数超过限制的IP
- Prototype Chain
- CSS让图标变成白色或黑色实例页面 和css变灰色
- 【构建二叉树】02根据中序和后序序列构造二叉树【Construct Binary Tree from Inorder and Postorder Traversal】
- 用nginx搭建http/rtmp/hls协议的MP4/FLV流媒体服务器
- “Hello World”—— 第一个汇编程序
- Redo Log File(inactive、active)损坏,处理恢复对策
- MySQL on Azure高可用性设计 DRBD - Corosync - Pacemaker - CRM (二)