Rockdu's Blog

题意翻译

描述

掷骰子是一种双人游戏，它的结果是完全随机的。最近它在整个Byteotia变得非常流行。在Byteotia的首都甚至有一个特别的掷骰子业余爱好者俱乐部。俱乐部的老主顾们花时间互相聊天并每隔一阵子就和一个随机选择的对手玩这他们最喜欢的游戏。一天中赢得最多游戏的人会得到“幸运者”头衔。有时晚上俱乐部很安静，只有很少的比赛。这是哪怕赢一场也能获得“幸运者”头衔的时间。

很久很久以前有一个很不走运的人，叫Byteasar，赢得了这个光荣的头衔。他被深深地震惊了以至于完全忘了他已经赢了多少场。现在他想知道他有多幸运，以及幸运之神是否最终会向他微笑——也许他的运气会变好？他确切地知道在那个幸运的晚上有多少场游戏以及是谁玩的。然而，他不知道结果。Byteasar希望查明至少要赢几场才能获得“幸运者”头衔。做个好人，帮他满足他的好奇心吧！

任务：写一个程序：

对于每场游戏从stdin读入这场游戏的一对玩家 找到最小的数k，使得存在一个游戏结果的集合，其中赢最多的玩家赢了k场。向stdout输出数k和找到的集合中游戏的结果

输入

stdin的第一行有一个一对由一个空格分开整数n和m (1 <= n, m <= 10000) 。n表示玩家数，m表示游戏数。玩家从1到n编号。在接下来的m行中有每场游戏的一对玩家的编号，由一个空格分开，描述了游戏的序列。一对玩家可能会在这个序列中多次出现。

输出

stdout的第一行应该包含一个确定的数k。对于在输入的第i行指定的一对玩家a, b，如果在找到的结果集合中a胜过b，则在输出的第i行输出1, 否则输出0.

感谢 @zyt1253679098 提供的翻译。

题目描述

Dicing is a two-player game and its outcome is fully random. Lately its popularity increases all over Byteotia. There is even a special club for dicing amateurs in the capital city of Byteotia. The club patrons take their time talking to each other and playing their favourite game with a randomly chosen opponent every once in a while. Everyone who wins the most games one day gains the title of the lucky chap. Sometimes it happens that the night at the club is a quiet one and only few games are played. It is a time when even one win can make you a lucky chap.

Once upon a time a most unlucky fellow, Byteasar, won the glorious title. He was so deeply shocked that he completely forgot how many games he had won. Now he is wondering how good his luck was and whether fortune finally smiled upon him - perhaps his luck changed for good? He knows exactly how many games and between whom were played that lucky night. However, he does not know the results. Byteasar desires to find out what is the smallest number of wins that could provide the title of the lucky chap. Be a good fellow and help him satisfy his curiosity!

TaskWrite a programme that:

for each game played reads from the standard input the pair of players who competed in it.

finds the smallest number $k$ , such that a set of games' outcomes exists in which each player wins $k$ games at the most,writes the number $k$ and the results of games in the found set to the standard output.

Dicing 是一个两人玩的游戏,这个游戏在Byteotia非常流行. 甚至人们专门成立了这个游戏的一个俱乐部. 俱乐部的人时常在一起玩这个游戏然后评选出玩得最好的人.现在有一个非常不走运的家伙,他想成为那个玩的最好的人,他现在知道了所有比赛的安排,他想知道,在最好的情况下,他最少只需要赢几场就可以赢得冠军,即他想知道比赛以后赢的最多的那个家伙最少会赢多少场.

输入输出格式

输入格式：

In the first line of the standard input there is a pair of integers $n$ and $m$ separated by a single space, $1\le n\le 10000$ , $0\le m\le 10000$ ; $n$ denotes the number of players, while $m$ is the number of games. The players are numbered from $1$ to $n$ . In the following $m$ lines there are pairs of players' numbers depicting the sequence of games, separated by single spaces. One pair may occur many times in the sequence.

输出格式：

The first line of the standard output should contain the determined number $k$ . For each pair of players' numbers $a$ , $b$ specified in the $i$ 'th line of the input, in the $i$ 'th line of the output the number $1$ should be written if the player no. $a$ wins against player no. $b$ in the found set of outcomes, or $0$ otherwise.

输入输出样例

4 4
1 2
1 3
1 4
1 2

1
0
0
0
1​​

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
const int maxn = 1e5 + 5, inf = 0x3f3f3f3f;
using namespace std;
struct edge {
    int v, w, next;
}e[maxn << 1], E[maxn << 1];
int head[maxn], cnt;
void adde(const int &u, const int &v, const int &w) {
    E[cnt] = (edge) {v, w, head[u]};
    head[u] = cnt++;
    E[cnt] = (edge) {u, 0, head[v]};
    head[v] = cnt++;
}

int L[maxn], R[maxn], ncnt, n, m, u, v;
int win[maxn], dg[maxn], S, T, Us[maxn], Vs[maxn];
int Rst, Red, itr[maxn];

void Edit(int x) {
    for(register int i = Rst; i <= Red; i += 2)
        E[i].w = x;
    memcpy(e, E, sizeof(E));
}

int layer[maxn];
bool bfs(int S, int T) {
    queue<int > q;
    memset(layer, 0, sizeof(layer));
    memcpy(itr, head, sizeof(itr));
    q.push(S), layer[S] = 1;
    while(!q.empty()) {
        int u = q.front(), v;
        q.pop();
        for(register int i = head[u]; ~i; i = e[i].next) {
            v = e[i].v;
            if(layer[v] || !e[i].w) continue;
            layer[v] = layer[u] + 1;
            q.push(v);
        }
    }
    return layer[T];
}

int dfs(int u, int mn, int t) {
    if(u == t) return mn;
    int ret = 0, tmp;
    for(register int &i = itr[u]; ~i; i = e[i].next) {
        int v = e[i].v;
        if(!e[i].w || layer[v] != layer[u] + 1) continue;
        tmp = dfs(v, min(mn - ret, e[i].w), t);
        e[i].w -= tmp, e[i ^ 1].w += tmp, ret += tmp;
        if(ret == mn) return ret;
    }
    return ret;
}

int Dinic(int s, int t, int w) {
    int ans = 0;Edit(w);
    while(bfs(s, t)) ans += dfs(s, inf, t);
    return ans == m;
}

int id[maxn][2];
int main() {
    memset(head, -1, sizeof(head));
    scanf("%d%d", &n, &m);
    for(register int i = 1; i <= m; ++i)
        L[i] = ++ncnt;
    for(register int i = 1; i <= n; ++i)
        R[i] = ++ncnt;
    T = ++ncnt;
    for(register int i = 1; i <= m; ++i)
        scanf("%d%d", &Us[i], &Vs[i]);
    for(register int i = m; i >= 1; --i)
        adde(S, i, 1);
    for(register int i = m; i >= 1; --i) {
        adde(i, R[Us[i]], 1), id[i][0] = cnt - 1;
        adde(i, R[Vs[i]], 1), id[i][1] = cnt - 1;
    }
    Rst = cnt;
    for(register int i = 1; i <= n; ++i)
        adde(R[i], T, 1);
    Red = cnt - 1;
    int l = -1, r = m;
    while(l < r - 1) {
        int mid = l + r >> 1;
        if(Dinic(S, T, mid)) r = mid;
        else l = mid;
    }
    printf("%d\n", r);
    Dinic(S, T, r);
    for(register int i = 1; i <= m; ++i) {
        if(e[id[i][0]].w) putchar('1');
        else putchar('0');
        putchar('\n');
    }
    return 0;
}

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<queue> const int maxn = 1e5 + 5, inf = 0x3f3f3f3f; using namespace std; struct edge { int v, w, next; }e[maxn << 1], E[maxn << 1]; int head[maxn], cnt; void adde(const int &u, const int &v, const int &w) { E[cnt] = (edge) {v, w, head[u]}; head[u] = cnt++; E[cnt] = (edge) {u, 0, head[v]}; head[v] = cnt++; } int L[maxn], R[maxn], ncnt, n, m, u, v; int win[maxn], dg[maxn], S, T, Us[maxn], Vs[maxn]; int Rst, Red, itr[maxn]; void Edit(int x) { for(register int i = Rst; i <= Red; i += 2) E[i].w = x; memcpy(e, E, sizeof(E)); } int layer[maxn]; bool bfs(int S, int T) { queue<int > q; memset(layer, 0, sizeof(layer)); memcpy(itr, head, sizeof(itr)); q.push(S), layer[S] = 1; while(!q.empty()) { int u = q.front(), v; q.pop(); for(register int i = head[u]; ~i; i = e[i].next) { v = e[i].v; if(layer[v] || !e[i].w) continue; layer[v] = layer[u] + 1; q.push(v); } } return layer[T]; } int dfs(int u, int mn, int t) { if(u == t) return mn; int ret = 0, tmp; for(register int &i = itr[u]; ~i; i = e[i].next) { int v = e[i].v; if(!e[i].w || layer[v] != layer[u] + 1) continue; tmp = dfs(v, min(mn - ret, e[i].w), t); e[i].w -= tmp, e[i ^ 1].w += tmp, ret += tmp; if(ret == mn) return ret; } return ret; } int Dinic(int s, int t, int w) { int ans = 0;Edit(w); while(bfs(s, t)) ans += dfs(s, inf, t); return ans == m; } int id[maxn][2]; int main() { memset(head, -1, sizeof(head)); scanf("%d%d", &n, &m); for(register int i = 1; i <= m; ++i) L[i] = ++ncnt; for(register int i = 1; i <= n; ++i) R[i] = ++ncnt; T = ++ncnt; for(register int i = 1; i <= m; ++i) scanf("%d%d", &Us[i], &Vs[i]); for(register int i = m; i >= 1; --i) adde(S, i, 1); for(register int i = m; i >= 1; --i) { adde(i, R[Us[i]], 1), id[i][0] = cnt - 1; adde(i, R[Vs[i]], 1), id[i][1] = cnt - 1; } Rst = cnt; for(register int i = 1; i <= n; ++i) adde(R[i], T, 1); Red = cnt - 1; int l = -1, r = m; while(l < r - 1) { int mid = l + r >> 1; if(Dinic(S, T, mid)) r = mid; else l = mid; } printf("%d\n", r); Dinic(S, T, r); for(register int i = 1; i <= m; ++i) { if(e[id[i][0]].w) putchar('1'); else putchar('0'); putchar('\n'); } return 0; }