题解 :
众所周知, BZOJ的SPJ常常可以被puts("nan");过掉
所以对于第一问, 我们跑一遍已经建好图的dinic, 第二问直接puts("nan");就可以拿到本题的rank1辣!
正常一点的题解 :
第一问直接跑个网络流就可以
第二问, BOB的最优策略当然是把P全加在Alice流完之后流量最大的的一条边上, 其他边都是0
所以我们只要保证在最大流不变的情况下令每条边的最大流量尽可能的小, 考虑二分答案.
对于当前的mid, 和一条边(u, v, flow), 我们只连接(u, v,\min(mid, flow)), 然后跑最大流,
若当前最大流和原图最大流相等, 则这个mid合法, 继续二分即可
最后答案就是l\times P
代码 :
然鹅并没有正常一点的代码
#include
#include
#include
#include
#include
using namespace std;
const int INF = 1<<30;
#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 100000, stdin), p1==p2)?EOF:*p1++)
char buf[100000], *p1, *p2;
const int N = 110;
int S, T;
inline int rd() {
int x = 0; char ch = nc();
while(!isdigit(ch)) ch = nc();
while(isdigit(ch)) x = ((x+(x<<2))<<1)+(ch^48), ch = nc();
return x;
}
#define rev(i, p) for(Edge *i = h[p]; i; i = i->next)
struct Edge {
int to, val;
Edge *next, *back;
}*h[N], e[N*20];
inline void addEdge(int u, int v, int w) {
static int _; Edge *
tmp = &e[++_]; tmp->to = v; tmp->val = w; tmp->next = h[u]; tmp->back = &e[_+1]; h[u] = tmp;
tmp = &e[++_]; tmp->to = u; tmp->val = 0; tmp->next = h[v]; tmp->back = &e[_-1]; h[v] = tmp;
}
int dep[N];
queue q;
bool bfs() {
memset(dep, 0, sizeof dep);
while(!q.empty()) q.pop();
dep[S] = 1; q.push(S);
while(!q.empty()) {
int u = q.front(); q.pop();
rev(i, u) if(!dep[i->to] && i->val) {
dep[i->to] = dep[u]+1;
if(i->to == T) return 1;
q.push(i->to);
}
}
return 0;
}
int dfs(int p, int mf) {
if(p == T) return mf;
int nf = 0;
rev(i, p) if(dep[i->to] == dep[p]+1 && i->val) {
int tmp = dfs(i->to, min(mf-nf, i->val));
if(!tmp) dep[i->to] = 0;
nf += tmp;
i->val -= tmp;
i->back->val += tmp;
if(nf == mf) break;
}
return nf;
}
inline int Dinic() {
int ans = 0, tmp;
while(bfs()) {
while((tmp=dfs(S, INF))) ans += tmp;
}
return ans;
}
int main() {
int n = rd(), m = rd(); rd(); S = 1, T = n;
for(int i = 1; i <= m; i ++ ) {
int u = rd(), v = rd(), w = rd();
addEdge(u, v, w);
}
printf("%d\nnan\n", Dinic());
}