【FJWC 2019】min
题目描述
给你一张 \(n\) 个点 \(m\) 条边的无向图，走过每条边都需要花费 \(1\) 秒。
给你一个整数 \(k\) ，请你选择至多 \(k\) 个点，令经过这些点也需要花费 \(1\) 秒，使得从点 \(0\) 走到点 \(n-1\) 的最短时间最大。输出这个最大值。
注意，不能选择点 \(0\) 或点 \(n-1\) 。
输入格式
第一行三个正整数 \(n,m,k\) ，意义见题面描述。
接下来 \(m\) 行，每行两个数 \(x,y\) ，表示 \(x\) 和 \(y\) 之间存在一条边，保证 \(0 \le x,y < n\) ，不存在重边和自环，且点 \(0\) 和点 \(n-1\) 连通。
样例输入
3 2 1
0 1
1 2
样例输出
3
\(2 \le n \le 100,1 \le m \le n \times (n-1)/2,0 \le k \le n\)
感觉对网络流相关知识太不熟练了，这种题都要写自闭。
题解二分有点神仙。
我的做法复杂度就不那么优秀了。首先找到最短路，然后我们要求出选最少的点使得\(0\)到\(n-1\)最短路\(+1\)。我们很容易发现就是要选出最少的点割断使得\(0\)和\(n-1\)不连通。
网络流啊!
每个点拆成两个，流量为一，其他在最短路上的边也要连上，流量\(\infty\)。
我们每次做完网络流过后随便求出一个最小割集，这些点就是我们选的点。然后我们重新跑最短路，重新建图。那些选了的点之间流量\(\infty\)，因为这些点不能再割了。
我们重复做，直到所有点选完或者\(k\)个点用完为止。
找出仍以一组最小割只需要从源点\(S\)出发，走富余边\(dfs\)一遍，得到点集\(\{S\}\)。如果一条满流边一个点\(\in\{S\}\),另一个不属于，那么这就是我们要选的点。
然而我智障地写了\(tarjan\)还有退流操作。。
代码：
#include<bits/stdc++.h>
#define ll long long
#define N 205
using namespace std;
inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}
int n,m,k;
struct road {
int to,next;
}s[N*N<<2];
int h[N],cnt;
void add(int i,int j) {s[++cnt]=(road) {j,h[i]};h[i]=cnt;}
int dis[N];
bool del[N];
struct node {
int v,d;
node() {v=d=0;}
node(int a,int b) {v=a,d=b;}
bool operator <(const node &a)const {
return d>a.d;
}
};
priority_queue<node>Q;
void dij() {
static bool in[N];
memset(dis,0x3f,sizeof(dis));
memset(in,0,sizeof(in));
dis[1]=0;
Q.push(node(1,0));
while(!Q.empty()) {
int v=Q.top().v;
Q.pop();
if(in[v]) continue ;
in[v]=1;
for(int i=h[v];i;i=s[i].next) {
int to=s[i].to;
if(in[to]) continue ;
if(dis[to]>dis[v]+1+del[to]) {
dis[to]=dis[v]+1+del[to];
Q.push(node(to,dis[to]));
}
}
}
}
int ans;
namespace dinic {
struct road {int to,next,f;}s[N*N<<2];
int h[N<<1],cnt=1;
int id[N];
void add(int i,int j,int f) {
s[++cnt]=(road) {j,h[i],f};h[i]=cnt;
s[++cnt]=(road) {i,h[j],0};h[j]=cnt;
}
int S,T;
int dis[N];
queue<int>q;
bool bfs(int S,int T) {
memset(dis,0x3f,sizeof(dis));
q.push(S);
dis[S]=0;
while(!q.empty()) {
int v=q.front();q.pop();
for(int i=h[v];i;i=s[i].next) {
int to=s[i].to;
if(s[i].f&&dis[to]>dis[v]+1) {
dis[to]=dis[v]+1;
q.push(to);
}
}
}
return dis[T]<1e9;
}
int dfs(int v,int maxf) {
if(v==T) return maxf;
int ret=0;
for(int i=h[v];i;i=s[i].next) {
int to=s[i].to;
if(s[i].f&&dis[to]==dis[v]+1) {
int dlt=dfs(to,min(maxf,s[i].f));
ret+=dlt;
s[i].f-=dlt;
s[i^1].f+=dlt;
maxf-=dlt;
if(!maxf) return ret;
}
}
return ret;
}
int dinic() {
int ans=0;
while(bfs(S,T)) {
while(1) {
int tem=dfs(S,1e9);
if(!tem) break ;
ans+=tem;
if(ans>=1e9) return ans;
}
}
return ans;
}
int dfn[N],low[N],tot;
int st[N],bel[N],scc;
bool ins[N];
void tarjan(int v) {
low[v]=dfn[v]=++tot;
ins[v]=1;
st[++st[0]]=v;
for(int i=h[v];i;i=s[i].next) {
int to=s[i].to;
if(!s[i].f) continue ;
if(!dfn[to]) {
tarjan(to);
low[v]=min(low[v],low[to]);
} else if(ins[to]) low[v]=min(low[v],dfn[to]);
}
if(dfn[v]==low[v]) {
scc++;
while(1) {
int j=st[st[0]--];
bel[j]=scc;
ins[j]=0;
if(j==v) break;
}
}
}
void Init() {
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
memset(ins,0,sizeof(ins));
memset(bel,0,sizeof(bel));
tot=scc=0;
}
void Tarjan() {
Init();
for(int i=1;i<2*n;i++)
if(!dfn[i]&&i!=n+1) tarjan(i);
}
vector<int>tem;
bool dfs(int v) {
if(v==T) return 1;
for(int i=h[v];i;i=s[i].next) {
int to=s[i].to;
if(s[i].f&&dfs(to)) return 1;
}
return 0;
}
void Cut() {
Tarjan();
tem.clear();
for(int i=2;i<n;i++) {
if(s[id[i]].f) continue ;
if(bel[i]!=bel[i+n]) {
S=i,T=1;
dinic();
S=n,T=i+n;
dinic();
tem.push_back(i);
del[i]=1;
s[id[i]].f=s[id[i]^1].f=0;
S=1,T=n;
dinic();
Tarjan();
}
}
}
void build() {
cnt=1;
memset(h,0,sizeof(h));
for(int i=2;i<n;i++) {
if(del[i]) add(i,i+n,1e9);
else add(i,i+n,1);
}
for(int v=1;v<n;v++) {
for(int i=::h[v];i;i=::s[i].next) {
int to=::s[i].to;
if(::dis[to]==::dis[v]+1+del[to]) {
if(v>1) add(v+n,to,1e9);
else add(v,to,1e9);
}
}
}
}
void solve() {
int res=k;
int tim=0;
while(1) {
S=1,T=n;
int now=dinic();
if(res<now) return ;
res-=now;
ans++;
Cut();
dij();
build();
}
return ;
}
}
int main() {
n=Get(),m=Get(),k=Get();
int a,b;
for(int i=1;i<=m;i++) {
a=Get()+1,b=Get()+1;
add(a,b),add(b,a);
}
dij();
for(int i=2;i<n;i++) {
dinic::id[i]=dinic::cnt+1;
dinic::add(i,i+n,1);
}
for(int v=1;v<n;v++) {
for(int i=h[v];i;i=s[i].next) {
int to=s[i].to;
if(dis[to]==dis[v]+1) {
if(v>1) dinic::add(v+n,to,1e9);
else dinic::add(v,to,1e9);
}
}
}
ans=dis[n];
dinic::solve();
cout<<ans<<"\n";
return 0;
}