## 【日常小测】最长路径

### 解题报告

1. 任意一个竞赛图一定存在哈密尔顿路径
2. 一个竞赛图存在哈密尔顿回路当且仅当这个竞赛图强连通

$ans_{x} = \sum\limits_{i = 1}^{x}{{{n – 1}\choose{i – 1}} g_i {{n – i}\choose{x – i}} f_{x – i} f_{n – x}}$

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 2009;

int n, MOD, f[N], g[N], pw[N * N], C[N][N];

char c = getchar();
int ret = 0, f = 1;
while (c < '0' || c > '9') {
f = c == '-'? -1: 1;
c = getchar();
}
while ('0' <= c && c <= '9') {
ret = ret * 10 + c - '0';
c = getchar();
}
return ret * f;
}

int main() {
freopen("path.in", "r", stdin);
freopen("path.out", "w", stdout);
pw[0] = 1;
for (int i = 1; i < n * n; i++) {
pw[i] = (pw[i - 1] << 1) % MOD;
}
C[0][0] = 1;
for (int i = 1; i <= n; ++i) {
C[i][0] = 1;
for (int j = 1; j <= n; j++) {
C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
}
}
f[0] = g[0] = 1;
for (int i = 1; i <= n; i++) {
f[i] = g[i] = pw[i * (i - 1) >> 1];
for (int j = 1; j < i; j++) {
g[i] = (g[i] - (LL)C[i][j] * g[j] % MOD * f[i - j]) % MOD;
}
}
for (int x = 1; x <= n; x++) {
int ans = 0;
for (int i = 1; i <= x; i++) {
ans = (ans + (LL)C[n - 1][i - 1] * g[i] % MOD * C[n - i][x - i] % MOD * f[x - i] % MOD * f[n - x]) % MOD;
}
printf("%d\n", ans > 0? ans: ans + MOD);
}
return 0;
}


## 【BZOJ 2095】[Poi2010] Bridges

#include<bits/stdc++.h>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
using namespace std;

const int N = 2000+9;
const int M = 10000+9;
const int INF = 1e9;

struct Edge{int u,v,w1,w2;}edge[M];
int n,m,MX,MN=INF,in[N],out[N],cur[M];
queue<int> que;

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}

inline void Add_Edge(int u, int v, int f) {
to[++TT] = v; nxt[TT] = head[u]; head[u] = TT; flow[TT] = f;
to[++TT] = u; nxt[TT] = head[v]; head[v] = TT; flow[TT] = 0;
}

inline bool BFS(){
memset(dis,-1,sizeof(dis));
dis[S] = 0; que.push(0);

while (!que.empty()) {
int w = que.front(); que.pop();
for (int i=head[w];i;i=nxt[i]) if (flow[i] && !~dis[to[i]]) {
dis[to[i]] = dis[w] + 1;
que.push(to[i]);
}
}

return ~dis[T];
}

int DFS(int w, int f) {
if (w == T) {
return f;
} else {
int ret = 0;
for (int &i=cur[w],tmp;i && f;i=nxt[i]) {
if (dis[to[i]] == dis[w] + 1) {
tmp = DFS(to[i], min(f, flow[i]));
ret += tmp; f -= tmp;
flow[i] -= tmp; flow[i^1] += tmp;
}
}
return ret;
}
}

inline int Dinic(){
int ret = 0;
while (BFS()) {
ret += DFS(S,INF);
}
return ret;
}

inline bool judge(int lim){
memset(in,0,sizeof(in));
memset(out,0,sizeof(out));
S = 0; T = N - 1; TT = 1;
int tot = 0;

for (int i=1;i<=m;i++) {
if (lim < edge[i].w1) {
continue;
} else if (lim < edge[i].w2) {
in[edge[i].v]++;
out[edge[i].u]++;
} else {
in[edge[i].v]++;
out[edge[i].u]++;
}
}

for (int i=1;i<=n;i++) {
if (abs(in[i]-out[i]) & 1) {
return false;
} else if (in[i] < out[i]) {
tot += out[i] - in[i];
} else if (in[i] > out[i]) {
}
}

return Dinic() == tot;
}

int main(){
for (int i=1;i<=m;i++) {
if (edge[i].w1 > edge[i].w2) {
swap(edge[i].w1, edge[i].w2);
swap(edge[i].u, edge[i].v);
}
MX = max(MX, edge[i].w2);
MN = min(MN, edge[i].w1);
}

int l = MN, r = MX, mid, ret = -1;
while (l <= r) {
mid = l + r >> 1;
if (judge(mid)) ret = mid, r = mid - 1;
else l = mid + 1;
}
if (~ret) printf("%d\n",ret);
else puts("NIE");
return 0;
}