网络流：
模板（EK）：好像EK就够快了
#include<bits/stdc++.h>
using namespace std;
long long n,m,u[100005],v[100005],w[100005],head[100005],nex[100005],cnt=1,s,t,ans,fl[505][505],vis[505],pre[505],id,to,dis[100005];
queue<long long> Q;
void add(long long a,long long b,long long c)
{
cnt++;
u[cnt]=a,v[cnt]=b,w[cnt]=c;
nex[cnt]=head[u[cnt]];
head[u[cnt]]=cnt;
}
long long bfs()
{
for(long long i=s;i<=t;i++) vis[i]=pre[i]=0;
dis[s]=114514191810;
while(!Q.empty()) Q.pop();
vis[s]=1;
Q.push(s);
while(!Q.empty())
{
id=Q.front();
Q.pop();
//cout<<id<<endl;
for(long long i=head[id];i!=0;i=nex[i])
{
to=v[i];
// cout<<to<<endl;
if(w[i]>0)
{
if(vis[to]==0)
{
dis[to]=min(dis[id],w[i]);
vis[to]=1;
Q.push(to);
pre[to]=i;
if(to==t) return 1;
}
}
}
}
//cout<<'1';
return 0;
}
void update()
{
ans+=dis[t];
id=t;
while(id!=s)
{
w[pre[id]]-=dis[t];
w[pre[id]^1]+=dis[t];
id=u[pre[id]];
}
return ;
}
void EK()
{
while(bfs()!=0)
{
update();
}
}
int main()
{
return 0;
}
费用流：（EK加当前势优化dijk，很快）
#include<bits/stdc++.h>
using namespace std;
priority_queue<pair<long long,long long> > q;
long long flow,minn,ni[105][105],m,ans1;
long long to[114514],hu,hv,vis[114514],dis[114514],h[114514],k=1,n,a[105][105],ans,rd[10005],s=1,t=114514,u[114514],v[114514],w[114514],fl[114514],head[114514],nex[114514],cnt=1;
void add(int uu,int vv,int ww,int ffl)
{
k++;
u[k]=uu,v[k]=vv,w[k]=ww,fl[k]=ffl;
nex[k]=head[u[k]];
head[u[k]]=k;
k++;
u[k]=vv,v[k]=uu,w[k]=-ww,fl[k]=0;
nex[k]=head[u[k]];
head[u[k]]=k;
}
int dijk()
{
for(int i=s;i<=t;i++)
{
dis[i]=1145141919810;
vis[i]=0;
}
dis[s]=0;
q.push(make_pair(-dis[s],s));
while(!q.empty())
{
hu=q.top().second;
q.pop();
if(vis[hu]==0)
{
vis[hu]=1;
for(int i=head[hu];i!=0;i=nex[i])
{
hv=v[i];
if(vis[hv]==0)
{
if(dis[hu]+h[hu]-h[hv]+w[i]<dis[hv]&&fl[i]>=1)
{
dis[hv]=dis[hu]+h[hu]-h[hv]+w[i];
q.push(make_pair(-dis[hv],hv));
to[hv]=i;
}
}
}
}
}
if(dis[t]==1145141919810) return 0;
else return 1;
}
void FLY()
{
dijk();
for(int i=s;i<=t;i++) h[i]=dis[i];
while(dijk())
{
for(int i=s;i<=t;i++) h[i]=h[i]+dis[i];
minn=1145141919810;
for(int i=t;i!=s;i=u[to[i]])
{
minn=min(minn,fl[to[i]]);
}
for(int i=t;i!=s;i=u[to[i]])
{
fl[to[i]]-=minn;
fl[to[i]^1]+=minn;
}
ans+=minn*h[t];
ans1+=minn;
}
}
int main()
{
// freopen("P3381_8.in","r",stdin);
// freopen("compete.out","w",stdout);
//FLY();
return 0;
}