BZOJ 25九七 剪刀石头布(最小成本最大流)(WC2007)

在有的一对一游戏的竞赛(如下棋、乒球和羽球的单打)中,大家日常会赶上A胜过B,B胜过C而C又胜过A的有趣场地,不妨形象的叫做剪刀石头布景况。有的时候,无聊的人们会津津乐道于总计有稍许那样的剪刀石头布事态发生,即有多少对无序安慕希组(A, B,
C),满意当中的1位在竞赛中赢了另一位,另一位赢了第4个人而第陆位又胜过了第二私家。注意这里无序的情致是说长富组凉月素的各样并不根本,将(A,
B, C)、(A, C, B)、(B, A, C)、(B, C, A)、(C, A, B)和(C, B,
A)视为等同的情状。

Sample Input

2 4 2
7 6 6 7
10 5 20 15

 

Http

Luogu:https://www.luogu.org/problem/show?pid=1309

代码(896MS):

Description

在双人对决的比赛性比赛,如台球、羽球、国际象棋中,最广大的比赛制度是淘汰赛和循环赛。前者的特点是比赛管数少,每场都浮动刺激,但偶然性较高。后者的特色是相比公平,偶然性较低,但比赛进度往往卓殊冗长。

核心中牵线的瑞士联邦轮比赛制度,因最早选取于18玖伍年在瑞士联邦实行的国际象棋比赛而得名。它可以看做是淘汰赛与循环赛的投降,既保障了比赛的安澜,又能使比赛日程不至于过长。
2*N 名编号为 一~二N
的健儿共展开汉兰达轮比赛。每轮竞赛开首前,以及独具竞技甘休后,都会依照总分从高到低对选手实行1次排行。选手的总分为率先轮开头前的上马分数加辰月在场过的持有竞技的得分和。总分壹样的,约定编号较小的运动员排行靠前。

每轮竞赛的胶着布置与该轮竞技初步前的排名有关:第二 名和第3 名、第 三名和第 肆名、……、第二K – 1 名和第 2K名、…… 、第3N – 壹名和第叁N名,各举行一场比赛。每场竞技胜者得1 分,负者得 0
分。也等于说除了第二轮以外,其它轮较量的配备均不可能事先鲜明,而是要取决于选手在事先交锋中的表现。

现给定每种选手的起先分数及其实力值,试总括在路虎极光 轮比赛过后,排行第 Q
的健儿编号是有点。咱们借使选手的实力值两两不相同,且每场比赛后实力值较高的总能获胜。

View Code

Source

分治,归并排序

出口文件的第2行开首有3个和输入文件中格式相同的NN列的数字矩阵。第(i+1)行第j个数字描述了ij中间的赛果,壹表示i赢了j,0表示i负于j,与输入矩阵差异的是,在那些矩阵中绝非表示竞赛尚未开始展览的数字2;对角线上的数字都以0。输出矩阵要保管合法,无法发生争执。

Output

出口唯有1行,包蕴三个平头,即Koleos 轮竞技甘休后,排名第 Q 的健儿的编号。

  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 }

Sample Output

1

在第(i+1)行的第j列的数字要是是一,则意味着i在已经发生的竞技后赢了j;该数字要是0,则意味着在曾经发生的竞技中i败于j;该数字是二,表示ij以内的竞赛尚未产生。数字矩阵对角线上的数字,即第(i+1)行第i列的数字都以0,它们只是是占位符号,未有其余意义。

Input

输入的首先行是三个正整数N、讴歌ZDX 、Q,每四个数里面用二个空格隔开,表示有
二*N 名选手、中华V 轮竞赛,以及我们关注的排名 Q。

第一行是二N 个非负整数s1, s贰, …, s二N,每多少个数里面用一个空格隔开分离,当中si 表示编号为i 的健儿的开始分数。 第一行是二N 个正整数w一 , w贰 , …,
w二N,每三个数以内用3个空格隔开分离,当中 wi 表示编号为i 的健儿的实力值。

图片 1图片 2

Luogu130玖 瑞士联邦轮(分治,归并排序)

Description

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

class PEOPLE//定义人的结构体
{
public:
    int point,w,num;
};

bool operator < (PEOPLE a,PEOPLE b)//重载小于运算符,因为要使用STL中的sort
{
    if (a.point==b.point)
        return a.num<b.num;
    else
        return a.point>b.point;
}

const int maxN=1000001;
const int inf=2147483647;

int n,R,Q;
PEOPLE A[maxN*2];//存放所有人
PEOPLE K1[maxN*2];//每轮后临时存放胜者
PEOPLE K2[maxN*2];//临时存放败者

int main()
{
    cin>>n>>R>>Q;
    for (int i=1;i<=n*2;i++)
        cin>>A[i].point;
    for (int i=1;i<=n*2;i++)
        cin>>A[i].w;
    for (int i=1;i<=n*2;i++)
        A[i].num=i;
    sort(&A[1],&A[2*n+1]);//第一轮前用一边快排
    for (int i=1;i<=R;i++)
    {
        for (int j=1;j<=2*n;j=j+2)
        {
            if (A[j].w>A[j+1].w)
            {
                K1[j/2+1]=A[j];//分别放入两个数组
                K2[j/2+1]=A[j+1];
                K1[j/2+1].point++;
            }
            else
            {
                K1[j/2+1]=A[j+1];
                K2[j/2+1]=A[j];
                K1[j/2+1].point++;
            }
        }
        int j1=1,j2=1;
        for (int j=1;j<=2*n;j++)//归并排序
            if ((j2>n)|| ((j1<=n)&&((K1[j1].point>K2[j2].point)||((K1[j1].point==K2[j2].point)&&(K1[j1].num<K2[j2].num))) )     )
            {
                A[j]=K1[j1];
                j1++;
            }
            else
            {
                A[j]=K2[j2];
                j2++;
            }
    }
    cout<<A[Q].num<<endl;
    return 0;
}

 

解决思路

刚看那道难点一定想到的是每一轮都全体以分数为率先首要字、编号为第2重要字排序2遍,但诸如此类必然会晚点,所以我们另寻办法。

因为每3遍交锋后胜者的分数都只+一,所以壹旦大家在每1轮过后把胜者和败者分别放入八个数组,大家会发现,它们分别都以衣冠优孟的。

故此为了利用好那脾性格,大家选拔归并排序,那样就不会爆时间了。

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

输入文件保险合法,不会生出争辨,当i≠j时,第(i+1)行第j列和第(j+1)行第i列的七个数字或许都以二,要么二个是02个是壹。

Output

 

Input

出口文件的第3行是多少个平头,表示在你安排的比赛结果中,现身了有些剪刀石头布情况。

 

输入文件的第3行是三个平头N,表示参预竞技的人口。

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

N民用插手一场这样的游玩的交锋,比赛日程规定专擅几个人以内都要拓展一场交锋:这样1起有场比赛。竞技已经开始展览了1有的,我们想了解在格外情形下,竞技甘休后最多会时有发生多少剪刀石头布情况。即给出已经发生的比赛结果,而你能够随便铺排剩下的比赛的结果,以赢得尽量多的剪刀石头布情况。

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