球调网络流
查看原帖
球调网络流
200044
JS_TZ_ZHR楼主2021/4/19 22:56

RT...WA了5个点

#include<bits/stdc++.h>
using namespace std;
int n,p,q,opt,s=1,t,dis[405],head[405],cnt,ans,now[405],tot;
struct node{
    int to,dis,nxt;
}e[10005];
bool dinic(){
    queue<int>q;
    q.push(s);
    for(int i=1;i<=t;i++)dis[i]=1e9;
    dis[s]=0;
    now[s]=head[s];
    while(!q.empty()){
        int x=q.front();
        q.pop();
        for(int i=head[x];i;i=e[i].nxt){
            int y=e[i].to;
            if(!e[i].dis||dis[y]!=1e9)continue;
            dis[y]=dis[x]+1;
            now[y]=head[y];
            if(y==t)return 1;
            q.push(y);
        }
    }
    return 0;
}
inline void add(int u,int v,int w){
    e[++cnt].nxt=head[u];
    head[u]=cnt;
    e[cnt].to=v,e[cnt].dis=w;
    e[++cnt].nxt=head[v];
    head[v]=cnt;
    e[cnt].to=u,e[cnt].dis=0;
}
int dfs(int x,int sum){
    if(x==t)return sum;
    int res=0,num;
    for(int i=now[x];sum&&i;i=e[i].nxt){
        now[x]=i;
        int y=e[i].to;
        if(!e[i].dis||(dis[y]!=dis[x]+1))continue;
        num=dfs(y,min(sum,e[i].dis));
        if(!num)dis[y]=1e9;
        e[i].dis-=num;
        e[i^1].dis+=num;
        res+=num;
        sum-=num;
    }
    return res;
}
int get1(int x){
    return 1+x;
}
int get2(int x){
    return 1+2*n+p+x;
}
int get3(int x){
    return 1+p+x;
}
int main(){
    cin>>n>>p>>q;
    s=1,t=2+2*n+p+q;
    for(int i=1;i<=p;i++)add(1,get1(i),1);
    for(int i=1;i<=q;i++)add(get2(i),t,1);
    for(int i=1;i<=n;i++)add(get3(i),get3(i)+n,1);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=p;j++){
            cin>>opt;
            if(opt==1)add(get1(j),get3(i),1);
        }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=q;j++){
            cin>>opt;
            if(opt==1)add(get3(i)+n,get2(j),1);
        }
    while(dinic()){
        ans+=dfs(s,1e9);
    }
    cout<<ans<<endl;
}
2021/4/19 22:56
加载中...