关键词:
Submit: 1153 Solved: 543
Description
Input
Output
Sample Input
0 1 2
0 0 2
2 2 0
Sample Output
0 1 0
0 0 1
1 0 0
HINT
100%的数据中,N≤ 100。
Source
图论 网络流 费用流
选定一个人在一场比赛中胜利, 相当于钦定这个点出度+1
我们知道在竞赛图中,最多有$C(n,3)$个三元环。
若一个点出度为w[i],那么它就少生成了$C(w[i],2)$个三元环关系
所以我们的目的是让$C(n,3)-sum_{i=1}^{n}C(w[i],2)$最小
C(w[i],2)=w[i]*(w[i]-1)/2=1+2+3+…+(w[i]-1)。对于每个选手节点i,假设当前已经赢了w[i]场,我们就先将 C(w[i],2)累计到sum中(其中sum表示非石头剪刀布的数目),从该选手节点向汇点连边,容量为1,费用依次为w[i],w[i]+1,w[i]+2......连多少条边呢?n条一定够用了。
——阿当
跑费用流就可以了
1 /*by SilverN*/ 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #include<vector> 8 #include<queue> 9 using namespace std; 10 const int mxn=150010; 11 int read(){ 12 int x=0,f=1;char ch=getchar(); 13 while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 14 while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} 15 return x*f; 16 } 17 struct edge{ 18 int u,v,nxt,f,w; 19 }e[mxn<<1]; 20 int hd[mxn],mct=1; 21 void add_edge(int u,int v,int c,int w){ 22 e[++mct].v=v;e[mct].u=u;e[mct].nxt=hd[u];hd[u]=mct;e[mct].f=c;e[mct].w=w;return; 23 } 24 void insert(int u,int v,int c,int w){ 25 add_edge(u,v,c,w);add_edge(v,u,0,-w);return; 26 } 27 int S,T; 28 bool inq[mxn],mark[mxn]; 29 int dis[30011],pre[mxn]; 30 queue<int>q; 31 bool SPFA(){ 32 memset(inq,0,sizeof inq); 33 memset(dis,0x3f,sizeof dis); 34 dis[T]=0;q.push(T);inq[T]=1; 35 while(!q.empty()){ 36 int u=q.front();q.pop();inq[u]=0; 37 for(int i=hd[u],v;i;i=e[i].nxt){ 38 v=e[i].v; 39 if(e[i^1].f && dis[v]>dis[u]-e[i].w){ 40 dis[v]=dis[u]-e[i].w; 41 if(!inq[v]){ 42 inq[v]=1; 43 q.push(v); 44 } 45 } 46 } 47 } 48 return (dis[S]==0x3f3f3f3f)?0:1; 49 } 50 int res=0; 51 int DFS(int u,int lim){ 52 if(u==T){inq[T]=1;return lim;} 53 inq[u]=1; 54 int f=0,tmp; 55 for(int i=hd[u];i;i=e[i].nxt){ 56 int v=e[i].v; 57 if(!inq[v] && e[i].f && dis[u]-e[i].w==dis[v]){ 58 tmp=DFS(v,min(lim,e[i].f)); 59 res+=tmp*e[i].w; 60 e[i].f-=tmp; 61 e[i^1].f+=tmp; 62 f+=tmp;lim-=tmp; 63 if(!lim)return f; 64 } 65 } 66 return f; 67 } 68 void mcf(){ 69 while(SPFA()){ 70 inq[T]=1; 71 while(inq[T]){ 72 memset(inq,0,sizeof inq); 73 DFS(S,0x3f3f3f3f); 74 } 75 } 76 return; 77 } 78 int n,cnt=0; 79 int mp[105][105]; 80 int eg[105][105]; 81 int w[105]; 82 int smm=0; 83 int main(){ 84 int i,j; 85 n=read(); 86 for(i=1;i<=n;i++) 87 for(j=1;j<=n;j++){ 88 mp[i][j]=read(); 89 if(i==j)continue; 90 if(mp[i][j]==1){++w[i];} 91 } 92 S=0;T=n*n/2+n+1;cnt=n; 93 for(i=1;i<n;i++) 94 for(j=i+1;j<=n;j++){ 95 if(mp[i][j]==2){ 96 ++cnt; 97 insert(S,cnt,1,0); 98 insert(cnt,i,1,0); 99 eg[i][j]=mct; 100 insert(cnt,j,1,0); 101 } 102 } 103 for(i=1;i<=n;i++){ 104 smm+=w[i]*(w[i]-1)/2; 105 for(j=0;j<n;j++){ 106 insert(i,T,1,w[i]+j); 107 // printf("add:%d ",mct); 108 } 109 } 110 int ans=n*(n-1)*(n-2)/6;//C(n,3) 111 mcf(); 112 // printf("ans:%d smm:%d res:%d ",ans,smm,res); 113 ans=ans-smm-res; 114 printf("%d ",ans); 115 for(i=1;i<=n;i++){ 116 for(j=i+1;j<=n;j++){ 117 if(mp[i][j]!=2)continue; 118 // printf("eg[%d][%d]:%d ",i,j,eg[i][j]); 119 // printf("f:%d ",e[eg[i][j]].f); 120 if(e[eg[i][j]].f)mp[i][j]=1; 121 else mp[i][j]=0; 122 mp[j][i]=mp[i][j]^1; 123 } 124 } 125 for(i=1;i<=n;i++){ 126 for(j=1;j<=n;j++) 127 printf("%d ",mp[i][j]); 128 printf(" "); 129 } 130 return 0; 131 }
bzoj2597:[wc2007]剪刀石头布(代码片段)
直接求不好求引入未知数,考虑采用补集转化对于一次非剪刀石头布的情况,定是一个人赢了另两个人若知道一个人共赢了多少人,那么就贡献了n*(n-1)/2种不同的情况更一般的,一个人如果多赢了一个人,他的新增的贡献就是他... 查看详情
[wc2007]剪刀石头布
[Wc2007]剪刀石头布http://www.lydsy.com/JudgeOnline/problem.php?id=2597TimeLimit: 20Sec MemoryLimit: 128MBSec SpecialJudgeDescription在一些一对一游戏的比赛(如下棋、乒乓球和羽毛球的单打)中,我们经常会遇 查看详情
2597:[wc2007]剪刀石头布(代码片段)
2597:[Wc2007]剪刀石头布链接分析: 费用流。 首先转化一下问题,整张图最优的情况是存在$C_n^3$个,即任意3个都行,然后考虑去掉最少不满足的三元环。 如果u赢了v,u向v连一条边,如果v有k条入边,那么说明少了... 查看详情
[wc2007]剪刀石头布
正着求不太好求,,但是不是剪刀石头布的又很好表示:三个人中恰好有一个人赢了两场。所以我们考虑让这种三元组数量最少使得剪刀石头布最多。 考虑一个人如果赢了i场,那么他对非剪刀石头布的... 查看详情
[wc2007]剪刀石头布(代码片段)
题解给出一个竞赛图的一些边,你需要定向剩下的边,使得形成的三元环最少\\(i\\)如果能赢\\(j\\)就连一条\\(i\\toj\\)的边可以发现直接统计三元环的总个数是十分困难的我们可以考虑反面计数\\(n\\)个点的竞赛图的三元环的最大个数... 查看详情
luogup4249[wc2007]剪刀石头布(代码片段)
Link先把题意抽象一下:给定一个存在一部分为定向的边的竞赛图,最大化它的三元环个数。我们知道竞赛图的三元环个数为(nchoose3-sumlimits_i=1^ndeg_ichoose2)。对于一条未定向的边((u,v)),它会使(u,v)其中一个点的度数加一。对于一个... 查看详情
[wc2007]剪刀石头布(代码片段)
洛古一句话题意:给定一张图,每两点之间有一条有向边或无向边,把所有无向边定向,使图中三元环个数尽量多因为原图是一个完全图,假设图中任意三点都能构成三元环,那么途中三元环的个数为:(inomn3)。那么如果一个三... 查看详情
剪刀石头布
usingSystem;usingSystem.Collections.Generic;usingSystem.Linq;usingSystem.Text;usingSystem.Threading.Tasks;usingWindowsFormsApp4;namespaceConsoleApp1{abstractclassBase{publicstringName{get;set;}publici 查看详情
python剪刀石头布(代码片段)
剪刀石头布游戏(代码片段)
...文明。矩阵上每个位置被三种生命形式之一占据:石头,剪刀,布。每天,上下左右相邻的不同生命形式将会发生战斗。在战斗中,石头永远胜剪刀,剪刀永远胜布,布永远胜石头。每一天结束之后,败者的领地将被胜者占领。... 查看详情
ytu2516:剪刀石头布
2516:剪刀石头布时间限制: 1Sec 内存限制: 128MB提交: 193 解决: 123题目描述小慧小时候很喜欢和她的小伙伴们一起玩剪刀(Scissors)、石头(Rock)、布(Cloth)的游戏,但现在她上大学了,和小伙伴们... 查看详情
《石头、剪刀、布》幼儿园教案
...案应该怎么写才合适呢?以下是我为大家整理的《石头、剪刀、布》幼儿园教案,希望能够帮助到大家。《石头、剪刀、布》幼儿园教案1 核心导读:适合年龄:大、中、小班幼儿。制作步骤:手的做法是:握紧拳头为石头... 查看详情
剪刀石头布(三局两胜)
....randint(0,2) people=int(input("请做出选择(0:石头1:剪刀2:布):")) ifcomputer==people==0: print("电脑:石头 玩家:石头 结果:平局") elifcomputer==people==1: &... 查看详情
剪刀石头布。使用数学确定赢/输/平?
】剪刀石头布。使用数学确定赢/输/平?【英文标题】:Rock,Paper,Scissors.Determinewin/loss/tieusingmath?【发布时间】:2012-07-0719:01:45【问题描述】:所以我在写这个函数的时候正在写一个石头剪刀布游戏:a是玩家一手,b是玩家二手。... 查看详情
scratch剪刀石头布
...以学做老hu机? 大于、等于、小于的比较,是不是和剪刀石头布的游戏很像呢?我们要学点健康的东西。好了,不会话了,我们开始:首先,因为一共只有3样东 查看详情
团队-石头,剪刀,布-设计文档
项目名称:石头,剪刀,布游戏项目参加人员:王聪、李宇鸿、李佳旭、余兴财、王佳傲、魏来项目所需环境及工具:androidstudio2.2页面设计:开始页面设置两个按钮,一个跳转到人机页面一个跳转到人人对战页面游戏功能设计... 查看详情
团队-石头,剪刀,布-设计文档
项目名称:石头,剪刀,布游戏项目参加人员:王聪、李宇鸿、李佳旭、余兴财、王佳傲、魏来项目所需环境及工具:androidstudio2.2页面设计:开始页面设置两个按钮,一个跳转到人机页面一个跳转到人人对战页面游戏功能设计... 查看详情
bzoj2597[wc2007]鍓垁鐭冲ご甯冣€斺€旇垂鐢ㄦ祦(代码片段)
鏍囩锛?ahref='http://www.mamicode.com/so/1/put'title='put'>put void mem 鎰忎箟 eof spfa name 瀹归噺 amp 棰樼洰锛?ahref="https://www... 查看详情