@[moye到碗里来](/space/show?uid=52576) 那是一般图的dinic复杂度...dinic跑二分图的复杂度能证明是n*sqrt(m)的emmm
by strangers @ 2018-07-12 11:18:09
@[strangers](/space/show?uid=52452) 我去看了一下,有一篇博客写的的确是那样..
by moye到碗里来 @ 2018-07-12 11:18:34
@[strangers](/space/show?uid=52452) @moye到碗里来那这么说我不用写匈牙利了呗（鸡冻）
by SkyLiYu @ 2018-07-12 11:19:44
@[moye到碗里来](/space/show?uid=52576) $dicnic$一般复杂度$O(VE^{2})$但是跑二分图复杂度会急减到$O(n\sqrt{m})$
by 小可爱三岁七 @ 2018-07-12 11:19:49
@[隔壁小邱](/space/show?uid=22539) 有的时候有基于匈牙利算法的贪心...例如NOI2009 变换序列...还是要了解一下的(大雾
by strangers @ 2018-07-12 11:21:29
@[小可爱三岁七](/space/show?uid=62490)
@[moye到碗里来](/space/show?uid=52576)
@[strangers](/space/show?uid=52452)
敢问诸位大佬我的Dinic是不是哪里写错了（好吧一定是这样QWQ)
by SkyLiYu @ 2018-07-12 11:22:17
@[strangers](/space/show?uid=52452) 可是我是联赛小渣渣，不考国赛啊（滑稽）
by SkyLiYu @ 2018-07-12 11:23:04
@[隔壁小邱](/space/show?uid=22539) 你把我的拿过去试一下呢...说不定是你常数写的太大了...
```
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f
struct node
{
int from,to,cap,flow;
};
vector<node>edges;
vector<int>load[10005];
int n,m,s,t;
int cur[10005];
int d[10005];
void add(int u,int v,int w)
{
edges.push_back((node){u,v,w,0});
edges.push_back((node){v,u,0,0});
int x=edges.size();
load[u].push_back(x-2);
load[v].push_back(x-1);
}
bool bfs()
{
memset(d,0,sizeof(d));
queue<int>q;
q.push(s);
d[s]=1;
while(!q.empty())
{
int u=q.front();q.pop();
int x=load[u].size();
for(register unsigned int i=0;i<x;i++)
{
node &v=edges[load[u][i]];
if(!d[v.to]&&v.cap>v.flow)
{
d[v.to]=d[u]+1;
q.push(v.to);
}
}
}
return d[t]!=0?1:0;
}
int dfs(int u,int mini)
{
if(mini==0||u==t)
return mini;
int x=load[u].size();
int flow=0;
for(register int &i=cur[u];i<x;i++)
{
node& v=edges[load[u][i]];
int f;
if(d[v.to]==d[u]+1&&(f=dfs(v.to,min(mini,v.cap-v.flow)))>0)
{
v.flow+=f;
edges[load[u][i]^1].flow-=f;
flow+=f;
mini-=f;
if(mini==0)break;
}
}
return flow;
}
void dinic()
{
int ans=0;
while(bfs())
{
memset(cur,0,sizeof(cur));
ans+=dfs(s,INF);
}
printf("%d",ans);
}
int main()
{
scanf("%d %d %d %d",&n,&m,&s,&t);
for(register unsigned int i=1;i<=m;i++)
{
int u,v,w;
scanf("%d %d %d",&u,&v,&w);
add(u,v,w);
}
dinic();
}
```
by moye到碗里来 @ 2018-07-12 11:23:14
@[moye到碗里来](/space/show?uid=52576) 老师有代码匹配，风格不一样，被他发现就……（你懂得）
by SkyLiYu @ 2018-07-12 11:25:12
@[moye到碗里来](/space/show?uid=52576) 还有，为啥您每次都说我大常数问题，这个大常数到底是个什么意思QWQ
by SkyLiYu @ 2018-07-12 11:26:04