为甚么第二个点过不去啊啊啊啊啊
查看原帖
为甚么第二个点过不去啊啊啊啊啊
147401
koishi_offical楼主2021/2/7 10:32
#include<bits/stdc++.h>
using namespace std;
const int inf=1<<29;
int n1,n2,n3,m1,m2,s=0,t=100000,h[100100],e[214514],ne[214514],w[214514],maxflow,d[100100],idx,now[100010];
void add(int a,int b,int c)
  {
      e[idx]=b;
      ne[idx]=h[a];
      h[a]=idx;
      w[idx++]=c;
      e[idx]=a;
      ne[idx]=h[b];
      h[b]=idx;
      w[idx++]=0;
  }
bool bfs() {
    queue<int> q;
    q.push(s);
    memset(d,0,sizeof(d));
    d[s]=1;
    now[s]=h[s];
    while(!q.empty())
      {
          int x=q.front();
          q.pop();
          for(int i=h[x];i!=-1;i=ne[i])
            if(w[i]&&!d[e[i]])
              {
                  now[e[i]]=h[e[i]];
                  q.push(e[i]);
                  d[e[i]]=d[x]+1;
                  if(e[i]==t) return 1;
              }
      }
    return 0;
}
int dinic(int x,int flow)
  {
      if(x==t) return flow;
      int rest=flow,k,i;
      for(int i=now[x];i!=-1&&rest;i=ne[i])
        if(w[i]&&d[e[i]]==d[x]+1)
          {
              k=dinic(e[i],min(w[i],rest));
              if(!k) d[e[i]]=0;
              w[i]-=k;
              w[i^1]+=k;
              rest-=k;
          }
    now[x]=i;
    return flow-rest;
  }
int main () {
    cin>>n1>>n2>>n3;
    memset(h,-1,sizeof(h));
    for(int i=1;i<=n1;i++) add(i,n1+i,1);
    for(int i=1;i<=n2;i++) add(s,n1*2+i,1);
    for(int i=1;i<=n3;i++) add(n1*2+n2+i,t,1);
    cin>>m1;
    for(int i=1;i<=m1;i++)
      {
      	int x,y;
      	cin>>x>>y;
      	add(n1*2+y,x,1);
      }
    cin>>m2;
    for(int i=1;i<=m2;i++)
      {
      	int x,y;
      	cin>>x>>y;
      	add(n1+x,n1*2+n2+y,1);
      }
    int flow=0;
    while(bfs())
      while(flow=dinic(s,inf)) maxflow+=flow;
   cout<<maxflow;
}

奉上丑逼代码

2021/2/7 10:32
加载中...