Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 随便写一下1h，居然1A了

Posted by TCtower at 2015-12-01 16:57:31 on Problem 2112
```代码
/*

*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <ctime>
#include <algorithm>
#include <queue>
#include <vector>
#define LOCAL
const int INF = (1 << 16);
const int MAXN = 500 + 10;
using namespace std;
struct Edge{
int u, v, c, f;
};
vector<int>G[MAXN];
vector<Edge>edge;
int K, C, M, n, s, t;
int data[MAXN][MAXN];
int vis[MAXN], d[MAXN], cur[MAXN];

void init(){
scanf("%d%d%d", &K, &C, &M);//K machine C cows and M positiion
n = (K + C);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++){
scanf("%d", &data[i][j]);
if (data[i][j] == 0) data[i][j] = INF;
}
//floyed
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++){
if (i == j) continue;
data[i][j] = min(data[i][j], data[i][k] + data[k][j]);
}
/*for (int i = 1; i <= n; i++){
for (int j = 1; j <= n; j++) printf("%d ", data[i][j] >= INF ? 0 :data[i][j]);
printf("\n");
}*/
}
void add(int u, int v, int w){
edge.push_back((Edge){u, v, w, 0});
edge.push_back((Edge){v, u, 0, 0});
int E = edge.size();
G[u].push_back(E - 2);
G[v].push_back(E - 1);
}
int bfs(){
memset(vis, 0, sizeof(vis));
queue<int>Q;
Q.push(s);
d[s] = 0;
vis[s] = 1;
while (!Q.empty()){
int u = Q.front();
Q.pop();
for (int i = 0; i < (int)G[u].size(); i++){
Edge &e = edge[G[u][i]];
if (!vis[e.v] && e.c > e.f){
vis[e.v] = 1;
d[e.v] = d[e.u] + 1;
Q.push(e.v);
}
}
}
return vis[t];
}
int dfs(int x, int a){
if (x == t || a == 0) return a;
int flow = 0, f;
for (int &i = cur[x]; i < (int)G[x].size(); i++){
Edge &e = edge[G[x][i]];
if (d[e.v] == d[e.u] + 1 && (f = dfs(e.v, min(a, e.c - e.f))) > 0){
e.f += f;
edge[G[x][i] ^ 1].f -= f;
flow += f;
a -= f;
if (a == 0) break;
}
}
return flow;
}
int Maxflow(){
int flow = 0;
while (bfs()){
memset(cur, 0, sizeof(cur));
flow += dfs(s, INF);
}
return flow;
}
int check(int x){
for (int i = 0; i <= n + 1; i++) {G[i].clear(); d[i] = INF;}
edge.clear();
for (int i = 1; i <= K; i++)//match the mac and the cows
for (int j = 1; j <= C; j++){
if (data[i][j + K] <= x) add(j + K, i, 1);
}
s = 0; t = n + 1;
for (int i = 1; i <= C; i++) add(s, i + K, 1);
for (int i = 1; i <= K; i++) add(i, t, M);
return Maxflow() == C;
}
void solve(){
int l = 1, r = INF, Ans = 0;
while (l <= r){
int mid = (l + r) >> 1;
if (check(mid)) Ans = mid, r = mid - 1;
else l = mid + 1;
}
printf("%d\n", Ans);
}

int main(){
#ifdef LOCAL
freopen("data.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif // LOCAL
init();
solve();
return 0;
}
```

Followed by: