澳门葡京集团网站BZOJ 2597 剪刀石头布(最小花费最大流)(WC2005)

时光过的真快,恍然之间,自身一度升高贰拾8周岁的三昧了。从前一直想不精晓,为啥小的时候觉得日子过的真慢,每一天想长大了,能够做家长做的那一个事情,比如不要挨打,比如上班赚钱,比如娶个媳妇等等。最近那一个都完成了,却觉得日子一天比一天过的快,快到甚至某些心惊胆战了,那么多的事体并未做,万一哪一天看到马克思了,真倒霉交待。直到读了李笑来老师的《把日子作为朋友》那本书(尤其推荐介绍各位去读下,肯定会有不等同的得到)才晓得,原来是与经验有关。5周岁长到陆岁的一年,占去了人生的五分之一,而二十八周岁到三九周岁的一年,去只占已走过人生的3%,20:3,那是多大的比重呀,也难怪觉得how
time flies!

Description

有时,想想过去的一年,是无比不佳的一年,是无限黯然的一年,是无与伦比失望的一年,是从未有过进步的一年。一直想写个小结,却直接从未下结论。那两天把温馨二〇一八年写的二零一二年的做事规划翻了出去,一条一条相比看了下:

在一些一对一游戏的比赛(如下棋、乒球和羽球的单打)中,大家平日会境遇A胜过B,B胜过C而C又胜过A的幽默场所,不要紧形象的名叫剪刀石头布情状。有的时候,无聊的大千世界会津津乐道于总结有微微那样的剪刀石头布情状产生,即有多少对无序安慕希组(A, B,
C),知足在那之中的1位在比赛前赢了另1位,另1位赢了第一个人而第伍人又胜过了第壹民用。注意那里无序的意味是说长富组瓜时素的相继并不根本,将(A,
B, C)、(A, C, B)、(B, A, C)、(B, C, A)、(C, A, B)和(C, B,
A)视为等同的场馆。

二〇一三年做事统一筹划与总括:

1.熟识运用ASP.NET MVC +jQuery+SQL Server
的网站开发架构。很好的姣好工作任务。要变成单位此架构下开发的主导人才和着力技术力量。在软件架构划设想计、代码编写方面有压实。

总计:那个差三错四,不敢拍胸口讲曾经形成了,但是多少算是应付过去了,只是私有对协调不佳听,觉得那中间依然有比比皆是亟需创新和学习的地点。

2.在座三月份“系统框架结构划设想计师”考试,争取获得证书,就算拿不到也要总分上完成供给,至少其中两门战表明到供给。

小结:那几个,只做了一件事,花钱买了框架结构划设想计的参考资料,其余什么都没干。其实考证不是温馨的目标,在存活公司,感觉学习提高上,有个别不便,一是半间半界,二是部门小,三是这么些城市的软件业也很相像。所以想透过以考促学。现在看来,这一个想法值得再细致商榷。

3.观看一本相比较经典的心境学书籍,调理个人的心思和心理。

计算:首要依旧想调适下个人的修改和心态,觉得在那地点有比较多的欠缺。但是,很遗憾,书是买了却从没看。

4.观看一本职场方面包车型大巴书籍,有利于团结的劳作和职业规划。

小结:结业就在当今那些单位工作四五年了,一贯觉得没有升高,无论是专业技能上,依然在品种管理上,还是在另内地方,就算偶尔也能取得领导和同事的认同,不过自个儿对团结的认同度始终不高,所以想在职场上有所改变。这么些是有行动,买了,也读了,而且连连一本,不止一回。但是,结果貌似也平素不多大的改进。

5.阅读一本时间管理方面包车型的士书本,更客观设计和接纳个人时间,学习时光管理。

总计:那一点有点凌乱,李笑来老师的书很好,个人计算下,便是决定大脑,做要好应当做的事。不过,说起容易,做起难,只可以逐步来吗。

6.阅读一本英文统计机专业书籍,升高英文阅读能力。

小结:那些纯真没有。

7.每一周至少一篇专业技术博客小说。

小结:这几个就非凡惭愧了,不用本身说,大家从小编的博客上也能观察,没有百折不回住。

8.在江山宗旨期刊杂志上录用或发布一篇学术杂文。

小结:那个,仔细想了下,算是吧,而且还费用了好多时刻。

9.要有每月总计。

总括:那么些,自从做了这几个二零一一年的平整,压根就从未有过写过一遍。

N个体插足一场那样的玩耍的交锋,比赛日程规定私自四个人之间都要开始展览一场交锋:那样一起有场比赛。竞赛一度拓展了一片段,大家想精晓在无限气象下,竞赛结束后最多会发出稍微剪刀石头布情景。即给出已经发生的比赛结果,而你能够随心所欲安排剩下的比赛的结果,以获取尽量多的剪刀石头布情况。

以上是对2011年规则的计算,真是惨不忍睹啊,没有实现的地点太多了。仔细分析下,大概存在三个方面的原由,一是陈设过高,这一年内无法完结,二是布署合适,只是人的题目而已。回头想想,除了“系统架构划设想计师”的考究算是相比较劳累的以外,别的没做好,多数恐怕因为个人原因。当然,这一年来,也有俯拾便是事务是团结不能控制的(起初找借口了),比如出差到实地支付多少个多月,基本没时间做别的交事务情。可是完全来说,照旧友好个人的缘故很多。二〇一四年又来了,上班已经1个多星期了,从过大年开头,就在盘算这一年的行事统一筹划,未来是该入手记下来了,尽管有点东西,写下来也不至于自身会自然执行,不过不写出来,不督促协调,很恐怕更促成持续。

Input

先说下本身干活儿四五年的感受啊。近期在南边2个共用性质的讨论所上班,首假如做.NET平台下的WinForm和Web开发,面向的客户都是些素质水平较低的用户(此处说的是新闻化素质,不是私人住房素质教养,相对没有其它贬低用户的情致),项目工作展开算不上顺遂。自身毕业后就来临了那一个单位,单位的管理水平和支出程度相比起来,就连塔林这样地点的大部IT集团来讲,都照旧有十分的大差异。那些年一直按领导的必要,做那做那,算得上并未进献也有苦劳的吧,可是在个人成长规划方面从未收获,单位也没有别的可供参考的饭碗成长安顿和职业技术培养和磨练机制。其实,那应当算是本身工作最头痛的地方,干了这一个年没有看出提高,不清楚以往的路怎么走。一起跻身的同事,包含后来的同事,也有不少跳走的,只是本人家曾经安在那儿了,想走也不容许的,即便换个单位,也不见得会比这几个好多少,再说,领导对本人也终究比较推崇,对自家个人在做事和生活上也好不简单相比接济,所以,最终依旧决定,在这前仆后继干下去。

输入文件的第②行是八个平头N,表示参与竞技的人头。

2014年,是再一次起始的一年,那段日子,自身也在学习东西,寒假买了些专业方面包车型大巴图书在读,主要的想法依然怎样升级本身,那大概也是办事几年但又不曾精神进展的心上人,都曾面临的难点吗。针对这一年的布署性,也写下来,给自身有些鞭策吧。

随后是2个NN列的数字矩阵:一共N行,每行N列,数字间用空格隔开分离。

2014工作规划:

1.对现有开发平台ASP.NET
MVC有比较深切的刺探,包括对前者设计与编码,都要有感觉获得、看得出来的发展。

2.读书项目管理的有关技术,今年有幸获得领导赏识,能够起来充当项目管理方面包车型客车一对干活了,要引发那么些空子,让投机抱有升高。

3.全心全意学习SQL
Server相关的学识。说实话自个儿对那地点很感兴趣,而且事先在那地点终于单位里驾驭的相比较好的壹位了,只是后来职务和动向太多,把它荒废了,而现年必将要优质在那地点发力。

4.调动工作心境,无论处在什么样境况,都要保持一颗积极向上的心气,二个为品种负责、为单位承担、为客户承担的心理,心态倒霉,什么都做不佳。而且你的办事态势怎样,就算再掩饰,同事也会看在眼里,藏在心尖的。

5.转移最近的行事场景,了解好什么是第①的事,什么是协调应该老将去做的事。学会时间管理的章程和优质的工作格局,国企切磋所那种单位,面对的是有些管理水平不太高的长官,有时候做起工作来,是很看不惯,不过尽力吧,缩小被她们不客观的牵着鼻子走的空子。指标是尽量少被打断,学会让他俩等一下,学会说不,学会做一个“专业”的软件人士(参考《The
Clean Coder》)。

6.自然每星期一篇博客,每月三个总括,这些依旧要走的,就算二〇一八年未曾坚韧不拔(准确点说是没有做),可是照旧有必不可少在当年接二连三开始展览下去的。养成三个可观的习惯,无论对工作照旧活着,都以老大有帮带的。

7.坚韧不拔阅读。小编欣赏阅读,也觉得阅读是四个很好的就学手段,特别是在以后这些环境下,也是为数不多可选的学习方式之一。二〇一九年一时半刻的开卷陈设有:

ASP.NET MVC4高档编程、
ASP.NET MVC4Web编程(在读)、
ASP.NET MVC4框架揭秘(在读,感觉以偏概全以偏概全,相比较费力,恐怕是因为个人水平原因吗)
编排可保障的JavaScript、
JavaScript语言精彩、
高功用程序员的修身(已读)、
程序员的饭碗素养(已读)、
高效开发1000零一夜(在读)、
高速软件开发:原则、形式与实践(C#修订版)、
敏捷技能修炼:敏捷开发与统一筹划的特等实践、
情势:工程化达成及增加(设计情势C#版)、
代码整洁之道(The Clean Code英文版,汉语版已经看过,觉得小编写的挺好)、
重构:改进既有代码的安排性(其实前边想看那一个,然则买了代码整洁之道)、
SQL Server 2013中肯解析与本性优化(第二版)、
多少挖掘与数据化运行实战:思路、方法、技艺与行使、
广阔分布式存款和储蓄系统:原理分析与框架结构实战、
一个程序员的奋斗史、
程序员,你伤不起、
伊斯兰堡麻将高级打法、

翻阅,要有阅读的情势,最大旨的三个便是要有读书笔记,通过它一是更精确地掌握里面包车型客车道理,二是可以做一些最首要音信的提炼,未来想看的时候,能够随手拈来,也惠及再一次学习。假设不做速记,只是读一次罢了,往往效果不见得理想。下边列的书目很多,貌似现在都有点一曝十寒了,可是不尝试何地能知晓啊。最想的恐怕,能沉下心来,仔细翻阅,有所收获吧。

8.乌Crane语学习。菲律宾语平昔未曾舍弃过,偶尔也会抽时间学习。二零一九年的指标是把ibt的单词背了,相关语教育学习下,压实据悉的操练,为下一步的想法做准备。

9.散文发布。因为职称评定审查的题材,不发布是老大的,国家基本刊物至少一篇吧。

10.磨炼身体。今年过大年病了一场,虽说一点都不大,但像自家这么从前连胃疼胃痛都基本没有的人,也总算一点都不小的一场吧。抓好磨练,至少每两周要打一遍羽球吧。

在第(i+1)行的第j列的数字假如是1,则代表i在曾经产生的竞技后赢了j;该数字即便0,则意味着在早就发生的竞赛中i败于j;该数字是2,表示ij里头的竞赛尚未产生。数字矩阵对角线上的数字,即第(i+1)行第i列的数字都以0,它们仅仅是占位符号,没有其余意义。

以上十条,是本人2015年的工作布置,至于今后3至5年的规划,就不贴了。总的来说,算是三个对团结的应允、勉励和监察吗,以期让本人能有所提升,也期望大家都能制定多少个布署,来年再看的时候,肯定会有不测的觉悟和取得。

输入文件保险合法,不会产生冲突,当i≠j时,第(i+1)行第j列和第(j+1)行第i列的四个数字也许都以2,要么1个是01个是1。

Output

输出文件的第贰行是1个平头,表示在您安插的比赛结果中,出现了多少剪刀石头布情况。

出口文件的第叁行开端有四个和输入文件中格式相同的NN列的数字矩阵。第(i+1)行第j个数字描述了ij以内的比赛结果,1意味着i赢了j,0表示i负于j,与输入矩阵差异的是,在那么些矩阵中没有代表比赛尚未开始展览的数字2;对角线上的数字都以0。输出矩阵要力保合法,不可能爆发争论。

 

题解:http://blog.csdn.net/pouy94/article/details/5972444

PS:那题太牛叉了值得一做……

 

代码(896MS):

澳门葡京集团网站 1澳门葡京集团网站 2

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <iostream>
  4 #include <algorithm>
  5 #include <queue>
  6 using namespace std;
  7 
  8 const int MAXN = 110;
  9 const int MAXV = MAXN * MAXN;
 10 const int MAXE = MAXN * MAXV;
 11 const int INF = 0x7f7f7f7f;
 12 
 13 struct ZWK_FLOW {
 14     int head[MAXV], dis[MAXV];
 15     int to[MAXE], next[MAXE], flow[MAXE], cost[MAXE];
 16     int n, ecnt, st, ed;
 17 
 18     void init() {
 19         memset(head, 0, sizeof(head));
 20         ecnt = 2;
 21     }
 22 
 23     void add_edge(int u, int v, int c, int w) {
 24         to[ecnt] = v; flow[ecnt] = c; cost[ecnt] = w; next[ecnt] = head[u]; head[u] = ecnt++;
 25         to[ecnt] = u; flow[ecnt] = 0; cost[ecnt] = -w; next[ecnt] = head[v]; head[v] = ecnt++;
 26         //printf("%d %d %d %d\n", u, v, c, w);
 27     }
 28 
 29     void spfa() {
 30         for(int i = 1; i <= n; ++i) dis[i] = INF;
 31         priority_queue<pair<int, int> > que;
 32         dis[st] = 0; que.push(make_pair(0, st));
 33         while(!que.empty()) {
 34             int u = que.top().second, d = -que.top().first; que.pop();
 35             if(d != dis[u]) continue;
 36             for(int p = head[u]; p; p = next[p]) {
 37                 int &v = to[p];
 38                 if(flow[p] && dis[v] > d + cost[p]) {
 39                     dis[v] = d + cost[p];
 40                     que.push(make_pair(-dis[v], v));
 41                 }
 42             }
 43         }
 44         int t = dis[ed];
 45         for(int i = 1; i <= n; ++i) dis[i] = t - dis[i];
 46     }
 47 
 48     int minCost, maxFlow;
 49     bool vis[MAXV];
 50 
 51     int add_flow(int u, int aug) {
 52         if(u == ed) {
 53             maxFlow += aug;
 54             minCost += dis[st] * aug;
 55             return aug;
 56         }
 57         vis[u] = true;
 58         int now = aug;
 59         for(int p = head[u]; p; p = next[p]) {
 60             int &v = to[p];
 61             if(flow[p] && !vis[v] && dis[u] == dis[v] + cost[p]) {
 62                 int t = add_flow(v, min(now, flow[p]));
 63                 flow[p] -= t;
 64                 flow[p ^ 1] += t;
 65                 now -= t;
 66                 if(!now) break;
 67             }
 68         }
 69         return aug - now;
 70     }
 71 
 72     bool modify_label() {
 73         int d = INF;
 74         for(int u = 1; u <= n; ++u) if(vis[u]) {
 75             for(int p = head[u]; p; p = next[p]) {
 76                 int &v = to[p];
 77                 if(flow[p] && !vis[v]) d = min(d, dis[v] + cost[p] - dis[u]);
 78             }
 79         }
 80         if(d == INF) return false;
 81         for(int i = 1; i <= n; ++i) if(vis[i]) dis[i] += d;
 82         return true;
 83     }
 84 
 85     int min_cost_flow(int ss, int tt, int nn) {
 86         st = ss, ed = tt, n = nn;
 87         minCost = maxFlow = 0;
 88         spfa();
 89         while(true) {
 90             while(true) {
 91                 for(int i = 1; i <= n; ++i) vis[i] = false;
 92                 if(!add_flow(st, INF)) break;
 93             }
 94             if(!modify_label()) break;
 95         }
 96         return minCost;
 97     }
 98 } G;
 99 
100 int n, m;
101 int mat[MAXN][MAXN], ans[MAXN][MAXN];
102 
103 inline int encode(int i, int j) {
104     if(i > j) swap(i, j);
105     return i * n + j;
106 }
107 
108 int main() {
109     scanf("%d", &n);
110     for(int i = 1; i <= n; ++i) for(int j = 1; j <= n; ++j) scanf("%d", &mat[i][j]);
111     m = n * n;
112     int ss = n + m + 1, tt = ss + 1;
113     G.init();
114     int sum = n * (n - 1) * (n - 2) / 6;
115     for(int i = 1; i <= n; ++i) {
116         for(int j = 1, tmp = 1; j < n; ++j, tmp += 2) G.add_edge(ss, i, 1, tmp);
117         for(int j = 1; j <= n; ++j) if(mat[i][j] != 0)
118             ans[i][j] = G.ecnt, G.add_edge(i, encode(i, j), 1, 0);
119     }
120     for(int i = 1; i <= m; ++i) G.add_edge(i + n, tt, 1, 0);
121     int x = G.min_cost_flow(ss, tt, tt);
122     printf("%d\n", sum - (x - n * (n - 1) / 2) / 2);
123     for(int i = 1; i <= n; ++i) {
124         for(int j = 1; j <= n; ++j) {
125             if(j != 1) printf(" ");
126             if(mat[i][j] != 2) printf("%d", mat[i][j]);
127             else {
128                 if(G.flow[ans[i][j]] == 0) printf("1");
129                 else printf("0");
130             }
131         }
132         puts("");
133     }
134 }

View Code