这份代码,跑起来65ms,Code by: Red_uncle
#include<bits/stdc++.h> // Test on : 66ms by Red_uncle
using namespace std;
int n,m,s,t;
typedef long long ll;
struct node{
int to;
ll w;
int nex;
}e[200005];
int cnt=1;
int head[200005];
ll dis[200005];
int now[200005];
int bfs(){
for(int i=1;i<=n;i++){
dis[i]=1e18;
}
dis[s]=0;
queue<int> p;
p.push(s);
now[s]=head[s];
while(!p.empty()){
int top=p.front();
p.pop();
for(int i=head[top];i;i=e[i].nex){
int y=e[i].to;
if(dis[y]>dis[top]+1&&e[i].w>0){
now[y]=head[y];
dis[y]=dis[top]+1;
p.push(y);
if(y==t){
return 1;
}
}
}
}
return 0;
}
ll dfs(int x,ll sum){
if(x==t)return sum;
ll res=0;
for(int i=now[x];i&&sum>0;i=e[i].nex){
int y=e[i].to;
now[x]=i;
if(dis[y]==dis[x]+1&&e[i].w>0){
ll k=dfs(y,min(sum,e[i].w));
e[i].w-=k;
e[i^1].w+=k;
sum-=k;
res+=k;
}
}
return res;
}
inline void add(int u,int v,ll w){
e[++cnt].nex=head[u];
e[cnt].to=v;
e[cnt].w=w;
head[u]=cnt;
e[++cnt].nex=head[v];
e[cnt].to=u;
e[cnt].w=0;
head[v]=cnt;
}
int main(){
cin>>n>>m>>s>>t;
for(int i=1;i<=m;i++){
int x,y;
ll w;
cin>>x>>y>>w;
add(x,y,w);
}
ll ans=0;
while(bfs()){
// cout<<1<<" "<<ans<<'\n';
ans+=dfs(s,1e18);
}
cout<<ans;
return 0;
}
而我的码这样↓,却847ms,凭什么....
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int N = 207;
typedef long long lli;
int n, m, S, T;
int x, y, z;
struct pot{
int v, nxt;
lli val;
}E[50*N];
int head[N], tot = 1;
inline void Add_edge(int u, int v, int val) {
E[++tot].v = v;
E[tot].val = val;
E[tot].nxt = head[u];
head[u] = tot;
}
int dep[N], cur[N];
inline bool bfs() {
queue <int> q;
q.push(S);
memset(dep, 0, sizeof(dep));
dep[S] = 1;
int u, v;
while(q.size()) {
u = q.front();
q.pop();
for(int i=head[u];i;i=E[i].nxt) {
v = E[i].v;
if(dep[v] || !E[i].val) continue;
dep[v] = dep[u] + 1;
q.push(v);
if(v == T) return true;
}
}
return false;
}
inline lli dfs(int u, lli nowflow) {
if(u == T) return nowflow;
if(nowflow == 0) return 0;
int v;
lli sum = 0, f;
for(int i=cur[u];i;i=E[i].nxt) {
v = E[i].v;
cur[u] = i;
if(dep[v] != dep[u]+1 || !E[i].val) continue;
f = dfs(v, min(E[i].val, nowflow));
E[i].val -= f;
E[i^1].val += f;
sum += f;
nowflow -= f;
}
return sum;
}
void Dinic() {
lli ans = 0;
while(bfs()) {
memcpy(cur, head, sizeof(cur));
ans += dfs(S, 0x3fffffffffffffff);
}
printf("%lld\n", ans);
}
int main() {
scanf("%d%d%d%d", &n, &m, &S, &T);
for(int i=1;i<=m;++i) {
scanf("%d%d%d", &x, &y, &z);
Add_edge(x, y, z);
Add_edge(y, x, 0);
}
Dinic();
return 0;
}
(无语子......)