萌新Dinic 求助
查看原帖
萌新Dinic 求助
70533
牛瓜瓜楼主2020/9/2 22:52

菜鸡不知道哪里写挂了/kel

挂了3 6 8 9 10刚好一般

求查错,万分感谢

#include<stdio.h>
#include<queue>
#include<cstring>
template<class TT>inline void read(TT &xx)
{
	xx=0;char cc=getchar();bool ff=false;
	while(cc<'0'||cc>'9'){if(cc=='-')ff=true; cc=getchar();}
	while(cc>='0'&&cc<='9'){xx=(xx<<3)+(xx<<1)+cc-'0';cc=getchar();}
	if(ff) xx=-xx;
}
namespace dinic
{
   using namespace std;
   #define inf 0x3f3f3f3f
   #define N 5013
   #define M 800010
   int head[N],ver[M],edge[M],nxt[M],d[N];
   bool v[N];
   int s,t,tot,ans;
   queue<int> q;
   void add(int x,int y,int z)
   {
      ver[++tot]=y;edge[tot]=z;nxt[tot]=head[x];head[x]=tot;
      ver[++tot]=x;edge[tot]=0;nxt[tot]=head[y];head[y]=tot;
   }
   bool bfs()
   {
      memset(d,0,sizeof(d));
      while(!q.empty()) q.pop();
      q.push(s);d[s]=1;
      while(!q.empty())
      {
         int x=q.front();q.pop();
         for(int i=head[x];i;i=nxt[i])
            if(edge[i] && !d[ver[i]])
            {
               q.push(ver[i]);
               d[ver[i]]=d[x]+1;
               if(ver[i]==t) return 1;
            }
      }
      return 0;
   }
   int dinic(int x,int flow)
   {
      if(x==t) return flow;
      int rest=flow,k;
      for(int i=head[x]; i&&rest; i=nxt[i])
         if(edge[i] && d[ver[i]]==d[x]+1)
         {
            k=dinic(ver[i],min(rest,edge[i]));
            if(!k) d[ver[i]]=0;
            edge[i]-=k;
            edge[i^1]+=k;
            rest-=k;
         }
      return flow-rest;
   }
   int get_ans()
   {
      ans=0;
      int flow=0;
      while(bfs())
      {
         while(flow=dinic(s,inf)) ans+=flow;
      }
      return ans;
   }
} /* dinic */
int n,m,e;
int main()
{
   freopen("bipartite.in","r",stdin);
   read(n);read(m);read(e);
   dinic::s=5000;
   dinic::t=5001;
   for(int i=1;i<=e;i++)
   {
      int x,y;
      read(x);read(y);
      //printf("%d %d\n",x,y);
      dinic::add(x,y+n,1);
   }
   for(int i=1;i<=n;i++)
      dinic::add(5000,i,1);
   for(int i=n+1;i<=n+m;i++)
      dinic::add(i,5001,1);
   printf("%d\n",dinic::get_ans());
   return 0;
}

2020/9/2 22:52
加载中...