求助 ABC318G
  • 板块学术版
  • 楼主shinzanmonoszm 妹妹
  • 当前回复2
  • 已保存回复2
  • 发布时间2023/9/3 00:15
  • 上次更新2023/11/2 23:44:56
查看原帖
求助 ABC318G
610557
shinzanmonoszm 妹妹楼主2023/9/3 00:15
#include<iostream>
#include<algorithm>
#include<queue>
const int sz=4e5+10;
struct edge{
    int nxt,to,w;
}graph[sz<<2];
int head[sz],chead[sz],hpp=1;
void addEdge(int from,int to,int w){
    graph[++hpp]=edge{head[from],to,w};
    head[from]=hpp;
}
int dep[sz],n,m,s,t;
bool bfs(){
    std::queue<int>qq;
    std::fill(dep,dep+2*n+2,0);
    std::copy(head,head+2*n+2,chead);
    dep[s]=1,qq.push(s);
    while(!qq.empty()){
        int u=qq.front();
        qq.pop();
        for(int p=head[u];p;p=graph[p].nxt){
            int v=graph[p].to;
            if(dep[v]==0&&graph[p].w!=0)dep[v]=dep[u]+1,qq.push(v);
        }
    }
    return dep[t]!=0;
}
int dfs(int u,int lim){
    if(u==t||lim==0)return lim;
    int arc=0,path=0;
    for(int p=chead[u];p&&lim;p=graph[p].nxt){
        chead[u]=p;
        int v=graph[p].to;
        if(dep[v]==dep[u]+1&&graph[p].w!=0){
            arc=dfs(v,std::min(graph[p].w,lim));
            lim-=arc,path+=arc;
            graph[p].w-=arc,graph[p^1].w+=arc;
        }
    }
    return path;
}
int dinic(){
    int ans=0;
    while(bfs())ans+=dfs(s,0x7fffffff);
    return ans;
}
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int a,b,c;
    std::cin>>n>>m>>a>>b>>c,t=2*n+1;
    addEdge(0,b,2),addEdge(b,0,0);
    addEdge(a+n,t,1),addEdge(t,a+n,0);
    addEdge(c+n,t,1),addEdge(t,c+n,0);
    for(int i=1;i<=n;i++)addEdge(i,i+n,1),addEdge(n+i,i,0);
    for(int i=1,u,v;i<=m;i++){
        std::cin>>u>>v;
        addEdge(u+n,v,1),addEdge(v,u+n,0);
        addEdge(v+n,u,1),addEdge(u,v+n,0);
    }
    if(dinic()==2)std::cout<<"Yes\n";
    else std::cout<<"No\n";
    return 0;
}
2023/9/3 00:15
加载中...