只有#9TLE掉了,用的dinic+弧优化,用的vector存边,还愿大佬赐教。
91分代码:
#include <bits/stdc++.h>
using namespace std;
long long n,m,s,t,ans=0;
long long minnn;
long long d[205];
vector<long long> ed[205];
struct edge{
long long u;
long long v;
long long w;
}e[100005];
int cur[100005];
bool bfs(){
bool flag=0;
memset(d,0,sizeof(d));
memset(cur,0,sizeof(cur));
queue<long long> q;
q.push(s);
d[s]=1;
while(!q.empty()){
long long u=q.front();
q.pop();
for(long long i=0;i<ed[u].size();i++){
long long v=e[ed[u][i]].v,w=e[ed[u][i]].w;
if(d[v])continue;
if(w<=0)continue;
d[v]=d[u]+1;
q.push(v);
if(v==t)flag=1;
}
}
return flag;
}
long long dfs(long long u,long long minn){
//cout<<u<<endl;
if(u==t)return minn;
long long k,rest=minn;
for(long long i=cur[u];i<ed[u].size();i++){
cur[u]=i;
long long v=e[ed[u][i]].v,w=e[ed[u][i]].w;
if(d[v]!=d[u]+1)continue;
if(w<=0)continue;
if(w)k=dfs(v,min(rest,w));
if(!k)d[v]=0;
e[ed[u][i]].w-=k;
e[ed[u][i]^1].w+=k;
rest-=k;
}
return minn-rest;
}
int main() {
std::ios::sync_with_stdio(0);
cin>>n>>m>>s>>t;
for(long long i=0;i<m;i++){
long long u,v,w;
cin>>u>>v>>w;
e[i*2].u=u;
e[i*2].v=v;
e[i*2].w=w;
e[i*2+1].u=v;
e[i*2+1].v=u;
e[i*2+1].w=0;
ed[u].push_back(i*2);
ed[v].push_back(i*2+1);
}
while(bfs()){
//for(long long i=1;i<=n;i++)cout<<d[i]<<' ';
//cout<<endl;
ans+=dfs(s,99999999);
//cout<<ans<<endl;
}
cout<<ans;
return 0;
}