社区讨论
求助,网络流做法,本地没事,交上去T飞了
P2764最小路径覆盖问题参与者 2已保存回复 2
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 2 条
- 当前快照
- 1 份
- 快照标识符
- @lo8eeka5
- 此快照首次捕获于
- 2023/10/27 17:15 2 年前
- 此快照最后确认于
- 2023/10/27 17:15 2 年前
#include<bits/stdc++.h>
using namespace std;
const int N=305,M=12505;
const int inf=0x3f3f3f3f;
int dist[N],flow[M],mfl=0;
int cur[N],head[N],nxt[M],to[M],tot=1,s,t;
int n,m,dep[N],f[N];
inline void add(int x,int y,int z){
to[++tot]=y;
nxt[tot]=head[x];
flow[tot]=z;
head[x]=tot;
}
inline bool bfs(){
memset(dep,0,sizeof(dep));
queue<int> q;
q.push(s);dep[s]=1;
while(q.size()){
int x=q.front();q.pop();
for(int i=head[x];i;i=nxt[i]){
int u=to[i];
if(dep[u]||!flow[i]) continue;
dep[u]=dep[x]+1;
q.push(u);
if(u==t) return 1;
}
}
return 0;
}
inline int dfs(int x,int now){
if(x==t) return now;
int res=inf;
for(int &i=cur[x];i;i=nxt[i]){
int u=to[i];
if(dep[u]<=dep[x]||!flow[i]) continue;
res=dfs(u,min(now,flow[i]));
if(!res) dep[u]=0;
else{
flow[i]-=res;
flow[i^1]+=res;
return res;
}
}
}
inline int find(int x){
return x==f[x]?x:f[x]=find(f[x]);
}
inline void un(int x,int y){
x=find(x),y=find(y);
if(x!=y) f[x]=y;
}
int main(){
scanf("%d%d",&n,&m);
t=n*2+1;
for(int i=1,x,y;i<=m;i++){
scanf("%d%d",&x,&y);
add(x,y+n,1);
add(y+n,x,0);
} for(int i=1;i<=n;++i){
add(s,i,1);
add(i,s,0);
add(i+n,t,1);
add(t,i+n,0);
}
while(bfs()){
for(int i=0;i<=t;i++) cur[i]=head[i];
while(int now=dfs(s,inf)) mfl+=now;
}
mfl=n-mfl;
for(int i=1;i<=n;++i) f[i]=i;
for(int i=1;i<=n;i++){
for(int j=head[i];j;j=nxt[j]){
if(!flow[j]&&to[j]-n<=n&&to[j]){
un(i,to[j]-n);
}
}
}
vector<int> ans[155];
for(int i=1;i<=n;i++){
ans[find(i)].push_back(i);
}
for(int i=1;i<=n;i++){
if(!ans[i].size()) continue;
for(auto u:ans[i]){
printf("%d ",u);
}
printf("\n");
}
printf("%d\n",mfl);
return 0;
}
回复
共 2 条回复,欢迎继续交流。
正在加载回复...