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

## 为什么RE

Posted by lolxu at 2016-07-26 15:44:13 on Problem 2112
```#include <iostream>
#include <cstdio>

using namespace std;

int n, C, M, K;
int dist[235][235];
const int inf = 1000000009;

#define MAXN 235
#define MAXE 12500
#define inf 0x3f3f3f3f
struct Edge{ int v,c,x; }E[MAXE]; //指向的节点, 剩余可增⼲⼴广的流量 int l[MAXN],e; //必须保证e的初始值是偶数 void init(){ e=0; memset(l,-1,sizeof(l)); }

int l[MAXN],e; //必须保证e的初始值是偶数

void init(){ e=0; memset(l,-1,sizeof(l)); }

inline void insert(int u,int v,int f,int invf){ //u->v=f
E[e].v=v; E[e].c=f;   E[e].x=l[u]; l[u]=e++;
E[e].v=u; E[e].c=invf;E[e].x=l[v]; l[v]=e++;
}

struct Netflow{
int src,sink; //需要初始化
//以上
int L[MAXN],Q[MAXN]; //L=level Q=queue
int _bfs(){ //广搜,并标记level(只取流量⼤大于0的边)
int s=0,t=0,u;
memset(L,0xff,sizeof(L));
L[src]=0; Q[t++]=src;
while (s<t){
u=Q[s++];
for (int p=l[u];p>=0;p=E[p].x)
if (E[p].c && L[E[p].v]==-1)
L[(Q[t++]=E[p].v)]=L[u]+1;
}
return L[sink]!=-1;
}
int _find(int u,int in){ //in:能流⼊入u节点的最⼤大流量. 返回u节点能流出的最⼤大流量 if (u==sink) return in;
int t,w=0; //w表⽰示已经从u流出的总流量
for (int p=l[u];p>=0 && w<in;p=E[p].x){
if (E[p].c>0 && L[E[p].v]==L[u]+1){
if (t=_find(E[p].v,min(E[p].c,in-w))){
E[ p].c-=t;
E[p^1].c+=t; //这⾥里表⽰示必须 w+=t; //多路增⼲⼴广优势巨⼤大
}
}
}
if( w<in )L[u]=-1;//关键的⼀一句话
return w;
}
int dinic(){
int t,res=0;
while (_bfs()) {
while (t=_find(src,inf))res+=t;
}
return res;
}
}flow; //********模板结束***********
//init(); insert(...); flow.src=.. ; flow.sink; flow.dinic();

bool check(int max_dist) {
init();
//1-K machines, K+1 - K+C, cows, C+K+1 source, C+K+2 sink
for (int i = 0; i < K; ++i) {
for (int j = K; j < K + C; ++j) {
//j cows, i machines
if (dist[i][j] <= max_dist) {
insert(j + 1, i + 1, inf, 0);
}
}
}
flow.src = K + C + 1;
flow.sink = K + C + 2;
for (int i = 1; i <= K; ++i) {
insert(i, flow.sink, M, 0);
}
for (int i = K + 1; i <= K + C; ++i) {
insert(flow.src, i, 1, 0);
}
int max_flow = flow.dinic();
if (max_flow == C) {
return true;
}
return false;
}

int main() {
while (scanf("%d%d%d", &K, &C, &M) != EOF) {
for (int i = 0; i < K + C; ++i) {
for (int j = 0; j < K + C; ++j) {
scanf("%d", &dist[i][j]);
if (dist[i][j] == 0) dist[i][j] = inf;
if (i == j) dist[i][j] = 0;
}
}
for (int k = 0; k < K + C; ++k) {
for (int i = 0; i < K + C; ++k) {
if (k == i) continue;
for (int j = 0; j < K + C; ++j) {
if (i == j || k == j) continue;
if (dist[i][k] + dist[k][j] <= dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}

int L = 0, R = inf;
while (L < R) {
int mid = L + (R - L) / 2;
bool flag = check(mid);
if (flag) {
R = mid;
} else {
L = mid;
}
}
int max_distance = L;
printf("%d\n", max_distance);

}
return 0;
}```

Followed by: