2022杭电多校（十）

2022杭电多校（十）

一、比赛小结

比赛链接：Problems (hdu.edu.cn)

二、题目分析及解法（基础题） 1001、Winner Prediction

题目链接：Problem - 7244 (hdu.edu.cn)

题意：

有 n 个人在打比赛，现在已经有 m1 场比赛胜负已定， 有 m 2 场比赛胜负未知，一个人获得冠军的条件是没有人赢得比赛的次数大于他，问 1 号选手是否有可能赢得冠军

题解：

先让 1 号选手赢下所有和他有关的比赛，设此时选手 i 赢了 a i a_i ai​ 场比赛。如果存在某个 a i > a i + 1 a_i>a_{i+1} ai​>ai+1​ 则 1 号选手不可能成为冠军。否则选手 i i i 至多还能再赢 b i = a 1 − a i b_i=a_1-a_i bi​=a1​−ai​ 场比赛。考虑建立一张网络流图：每场未进行的比赛在图中用一个点表示，源点向它连容量为 1 的边，它向它的两个参赛选手的对应点各自连容量为 1 的边；选手 i 的对应点向汇点连容量为 b i b_i bi​ 的边。计算该图最大流，若源点出发的边满流则答案为 YES ，否则为 NO 。

代码：

#include 
#include 
#include 
#include 
using namespace std;
const int N = 505;
int n, T, m1, m2, s[N];
namespace Flow {
struct Edge {
  int To, Val, Nxt;
} Ed[10005];
int n, S, T, Head[2005], cur[2005], dis[2005], cnt;
void AddEdge(int x, int y, int val) {
  // printf("AddEdge(%d,%d,%d)\n", x, y, val);
  Ed[++cnt] = (Edge){y, val, Head[x]};
  Head[x] = cnt;
  Ed[++cnt] = (Edge){x, 0, Head[y]};
  Head[y] = cnt;
}
bool bfs() {
  for (int i = 1; i  n;
    for (int i = 1; i > b[i], a[i] = b[i];
    // ↑ ↓
    // f == true -> up
    bool f1 = true;
    int ans1 = 0;
    for (int i = 2; i = a[i]) {
          ans1 += (a[i - 1] + 1 - a[i]);
          a[i] = a[i - 1] + 1;
        }
      } else {  // a[i] 应该下降
        if (a[i] >= a[i - 1]) {
          ans1 += (a[i] + 1 - a[i - 1]);
          a[i] = a[i - 1] - 1;
        }
      }
      f1 = !f1;
    }
    // ↓ ↑
    bool f2 = false;
    int ans2 = 0;
    for (int i = 2; i = b[i]) {
          ans2 += (b[i - 1] + 1 - b[i]);
          b[i] = b[i - 1] + 1;
        }
      } else {  // a[i] 应该下降
        if (b[i] >= b[i - 1]) {
          ans2 += (b[i] + 1 - b[i - 1]);
          b[i] = b[i - 1] - 1;
        }
      }
      f2 = !f2;
    }
    int ans = min(ans1, ans2);
    cout = 5) ans++;
    }
    cout