bzoj2561 最小割
Description
给定一个边带正权的连通无向图G=(V,E)，其中N=|V|，M=|E|，N个点从1到N依次编号，给定三个正整数u，v，和L (u≠v)，假设现在加入一条边权为L的边(u,v)，那么需要删掉最少多少条边，才能够使得这条边既可能出现在最小生成树上，也可能出现在最大生成树上？
Input
第一行包含用空格隔开的两个整数，分别为N和M；
接下来M行，每行包含三个正整数u，v和w表示图G存在一条边权为w的边(u,v)。
最后一行包含用空格隔开的三个整数，分别为u，v，和 L；
数据保证图中没有自环。
接下来M行，每行包含三个正整数u，v和w表示图G存在一条边权为w的边(u,v)。
最后一行包含用空格隔开的三个整数，分别为u，v，和 L；
数据保证图中没有自环。
Output
输出一行一个整数表示最少需要删掉的边的数量。
Sample Input
3 2
3 2 1
1 2 3
1 2 2
3 2 1
1 2 3
1 2 2
Sample Output
1
HINT
对于20%的数据满足N ≤ 10，M ≤ 20，L ≤ 20；
对于50%的数据满足N ≤ 300，M ≤ 3000，L ≤ 200；
对于100%的数据满足N ≤ 20000，M ≤ 200000，L ≤ 20000。
Source
一条边(u,v)可能在最小生成树上等价于当只有边权小于w(u,v)的边存在时，点u和点v不连通。
只将边权小于w(u,v)的边加入图中，每条边的边权设为1，那么u到v的最小割就是答案。
最大生成树同理。
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#define INF 1000000000
using namespace std;
inline int ReadInt()
{
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-') f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
inline int min(int x, int y)
{
if(x > y) return y;
else return x;
}
inline int max(int x, int y)
{
if(x < y) return y;
else return x;
}
struct data
{
int to,next,v;
}e[400010];
struct Node
{
int x,y,v;
}a[200010];
int cnt = 1, n, m, ans, U, V ,L;
int head[20010],cur[20010],h[20010],q[20010];
void ins(int u,int v,int w)
{
e[++ cnt].to = v;
e[cnt].next = head[u];
head[u] = cnt;
e[cnt].v = w;
}
void insert(int u,int v)
{
ins(u,v,1);
ins(v,u,1);
}
bool bfs()
{
int t = 0, w = 1;
memset(h,-1,sizeof(h));
h[U] = 0;
q[0] = U;
while(t != w)
{
int now = q[t];
t ++;
for(int i = head[now]; i; i = e[i].next)
if(e[i].v && h[e[i].to] == -1)
{
h[e[i].to] = h[now] + 1;
q[w ++] = e[i].to;
}
}
if(h[V] == -1)return 0;
return 1;
}
int dfs(int x,int f)
{
if(x == V)return f;
int w,used = 0;
for(int i = cur[x]; i; i = e[i].next)
if(h[e[i].to] == h[x] + 1)
{
w = f - used;
w = dfs(e[i].to,min(w,e[i].v));
e[i].v -= w;
if(e[i].v) cur[x] = i;
e[i^1].v += w;
used += w;
if(used == f)return f;
}
if(used == 0)h[x] = -1;
return used;
}
void dinic()
{
while(bfs())
{
for(int i = 1; i <= n; i ++)
cur[i] = head[i];
ans += dfs(U,INF);
}
}
int main()
{
n = ReadInt();
m = ReadInt();
for(int i = 1; i <= m; i ++)
a[i].x = ReadInt(),a[i].y = ReadInt(), a[i].v = ReadInt();
U = ReadInt(); V = ReadInt(); L = ReadInt();
for(int i = 1; i <= m; i ++)
if(a[i].v < L) insert(a[i].x, a[i].y);
dinic();
memset(head, 0, sizeof(head));
cnt = 1;
for(int i = m; i; i --)
if(a[i].v > L) insert(a[i].x,a[i].y);
dinic();
printf("%d",ans);
return 0;
}
投递字节跳动等公司9个岗位