dinic91/84pts求调

RT,这是原来的代码（91pts,TLE on #9)

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF=2147483647;
int x[10005],y[10005],z[10005],n,m,s,t,c[10005],lsm,ans;
vector<int>q[10005];
queue<int>p;
bool inline bfs(int s){
    memset(c,0,sizeof(c));
    c[s]=1;
    p.push(s);
    while(!p.empty()){
        lsm=p.front();
        p.pop();
        for(int i=0;i<q[lsm].size();i++)
            if(z[q[lsm][i]]>0&&c[y[q[lsm][i]]]==0){
                c[y[q[lsm][i]]]=c[lsm]+1;
                p.push(y[q[lsm][i]]);
            }
    }
    if(c[t]>0)return 1;
    return 0;
}
int inline dfs(int xx,int noww){
    int ul=0,qw=0;
    if(xx==t){
    ans+=noww;
    return noww;}
    for(int i=0;i<q[xx].size();i++){
        if(c[xx]<c[y[q[xx][i]]]&&z[q[xx][i]]>0&&noww>0){        
        qw=dfs(y[q[xx][i]],min(noww,z[q[xx][i]]));
        ul+=qw;
        noww-=qw;
        z[q[xx][i]]-=qw;
        z[q[xx][i]^1]+=qw;
        }
    }
    return ul;
}
signed main(){
    cin>>n>>m>>s>>t;
    for(int i=1;i<=m;i++){
        cin>>x[i*2+1]>>y[i*2+1]>>z[i*2+1];
        x[i<<1]=y[i*2+1],y[i<<1]=x[i*2+1],z[i<<1]=0;
        q[x[i*2+1]].push_back(i*2+1);
        q[y[i*2+1]].push_back(i<<1);
    }
    while(bfs(s)){
        dfs(s,INF);
    }
    cout<<ans<<endl;
}

然后加了几个剪枝后变成84pts（TLE ON #9 #10）

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF=2147483647;
int x[10005],y[10005],z[10005],n,m,s,t,c[10005],lsm,ans,dq[10005],wz[10005];
vector<int>q[10005];
queue<int>p;
bool inline bfs(int s){
    memset(c,0,sizeof(c));
    c[s]=1;
    p.push(s);
    while(!p.empty()){
        lsm=p.front();
        p.pop();
        for(int i=0;i<q[lsm].size();i++)
            if(z[q[lsm][i]]>0&&c[y[q[lsm][i]]]==0){
                c[y[q[lsm][i]]]=c[lsm]+1;
                p.push(y[q[lsm][i]]);
            }
    }
    if(c[t]>0)return 1;
    return 0;
}
int inline dfs(int xx,int noww){
    int ul=0,qw=0;
    if(xx==t){
    ans+=noww;
    return noww;}
    for(int i=dq[xx];i<q[xx].size();i++){
        if(noww==0)return ul;
        if(c[xx]<c[y[q[xx][i]]]&&z[q[xx][i]]>0&&noww>0){        
        qw=dfs(y[q[xx][i]],min(noww,z[q[xx][i]]));
        if(qw==z[q[xx][i]]&&dq[xx]==i)
        dq[xx]++;
        ul+=qw;
        noww-=qw;
        z[q[xx][i]]-=qw;
        if(dq[y[q[xx][i]^1]]>wz[q[xx][i]]&&z[q[xx][i]^1]==0)
        dq[y[q[xx][i]^1]]=wz[q[xx][i]];
        z[q[xx][i]^1]+=qw;
        }
    }
    if(ul==0)c[xx]=0;
    return ul;
}
signed main(){
    cin>>n>>m>>s>>t;
    for(int i=1;i<=m;i++){
        cin>>x[i*2+1]>>y[i*2+1]>>z[i*2+1];
        x[i<<1]=y[i*2+1],y[i<<1]=x[i*2+1],z[i<<1]=0;        
        wz[i*2+1]=q[x[i*2+1]].size(),wz[i<<1]=q[y[i*2+1]].size();
        q[x[i*2+1]].push_back(i*2+1);
        q[y[i*2+1]].push_back(i<<1);
    }
    while(bfs(s)){
        dfs(s,INF);
    }
    cout<<ans<<endl;
}