@[HLPP](/space/show?uid=192837) 或许您可以尝试用您名字的算法
by NaCly_Fish @ 2019-04-22 23:17:03
匈牙利大法吼
by saipubw @ 2019-04-23 00:25:32
hlpp干嘛不写hlpp呢
by _虹_ @ 2019-04-23 06:54:54
写hlpp啊
by ghy21 @ 2019-04-23 07:48:17
你这是什么dinic。。。
by 142857cs @ 2019-04-23 07:50:10
HLPP为什么不写HLPP呢
by dreagonm @ 2019-04-23 08:20:39
@[142857cs](/space/show?uid=35760) 大佬教教蒟蒻咋写dinic
by HLPP @ 2019-04-24 20:58:20
@[HLPP](/space/show?uid=192837) flow=0的要直接return 0,别的问题应该对这题没有影响
by 142857cs @ 2019-04-24 21:01:58
增广的时候不要只增广一次就return,要在flow用完或者没法增广了再return,不过这题不用,肯定只能增广一次
by 142857cs @ 2019-04-24 21:06:06
@[142857cs](/space/show?uid=35760) 巨佬,我判断0了,但还是T了,您能不能帮我看看是不是建图有问题
```
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
using std::queue;
const int N=1e6+5;
#define re register
#define inf 0x7fffffff
template<class T>inline void read(T &x) {
T f=1;x=0;char s=getchar();
while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
while(s>='0'&&s<='9'){x=(x<<1)+(x<<3)+(s&15);s=getchar();}
x*=f;
}
template<class T>inline T min(T a,T b) { return a<b?a:b; }
struct Edge {
int u,v,w;
}e[N<<2];
int cnt=1,n,m,k,u,v,head[4004],dep[1001],cur[4004],s,t;
inline void addedge(int u,int v,int w) {e[++cnt].v=v;e[cnt].w=w;e[cnt].u=head[u];head[u]=cnt;}
inline bool bfs() {
memset(dep,0,sizeof(dep));
queue<int> q;
q.push(s);
dep[s]=1;
while(!q.empty()) {
int fr=q.front();q.pop();
for(int i=head[fr];i;i=e[i].u) {
int to=e[i].v;
if(!dep[to]&&e[i].w) {
dep[to]=dep[fr]+1;
q.push(to);
}
}
}
return dep[t];
}
inline int dfs(int x,int flow){
if(x==t||flow==0) return flow;
int rlow=0,to,d=0;
for(int &i=cur[x];i;i=e[i].u) {
to=e[i].v;
if(dep[to]==(dep[x]+1)&&e[i].w) {
if(d=dfs(to,min(flow,e[i].w))) {
e[i].w-=d;e[i^1].w+=d;
rlow+=d;flow-=d;
if(!flow) break;
}
}
}
return rlow;
}
inline int dinic() {
int rlow=0,maxflow=0;
while(bfs()) {
memcpy(cur,head,sizeof(head));
rlow=dfs(s,inf); maxflow+=rlow;
}
return maxflow;
}
int main() {
read(n);read(m);read(k);
s=1;t=n+m+2;
for(re int i=1;i<=k;i++) {
read(u);read(v);
if(u>n||v>m) continue;
addedge(u+1,v+n+1,1);addedge(v+n+1,u+1,0);
}
for(re int i=1;i<=n;i++) addedge(s,i+1,1),addedge(i+1,s,0);
for(re int i=1;i<=m;i++) addedge(i+n+1,t,1),addedge(t,i+n+1,0);
printf("%d",dinic());
}
```
by HLPP @ 2019-04-24 21:23:24