MCMF+快读+O2 #9 TLE求助

回复帖子

@gdjcwsk 2020-08-01 22:12 回复
#include <bits/stdc++.h>
using namespace std;
const int maxn=10000005,inf=0x3f3f3f3f;
int n,m;
int tot=1,lnk[maxn],cur[maxn],ter[maxn],nxt[maxn],cap[maxn],cost[maxn],dis[maxn],ret;
bool vis[maxn];
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    { 
        if(ch=='-')
        {
            f=-1;
        }
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<3)+(x<<1)+ch-'0';
        ch=getchar();
    }
    return x*f;
}
void add(int u, int v, int w, int c)
{
    ter[++tot]=v;
    nxt[tot]=lnk[u];
    lnk[u]=tot;
    cap[tot]=w;
    cost[tot]=c;
}
void addedge(int u,int v,int w,int c)
{
    add(u,v,w,c);
    add(v,u,0,-c);
}
bool spfa(int s,int t)
{
    memset(dis,0x3f,sizeof(dis));
    memcpy(cur,lnk,sizeof(lnk));
    queue<int>q;
    q.push(s);
    dis[s]=0;
    vis[s]=1;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=lnk[u];i!=0;i=nxt[i])
        {
            int v=ter[i];
            if(cap[i]!=0&&dis[v]>dis[u]+cost[i])
            {
                dis[v]=dis[u]+cost[i];
                if(vis[v]==0)
                {
                    q.push(v);
                    vis[v]=1;
                }
            }
        }
    }
    return dis[t]!=inf;
}
int dfs(int u,int t,int flow)
{
    if(u==t)
    {
        return flow;
    }
    vis[u]=1;
    int ans=0;
    for(int &i=cur[u];i!=0&&ans<flow;i=nxt[i])
    {
        int v=ter[i];
        if(vis[v]==0&&cap[i]!=0&&dis[v]==dis[u]+cost[i])
        {
            int x=dfs(v,t,min(cap[i],flow-ans));
            if(x!=0)
            {
                ret+=x*cost[i];
                cap[i]-=x;
                cap[i^1]+=x;
                ans+=x;
            }
        }
    }
    vis[u]=0;
    return ans;
}
int mcmf(int s,int t)
{
    int ans=0;
    while(spfa(s,t)==1)
    {
        int x;
        while((x=dfs(s,t,inf)))
        {
            ans+=x;
        }
    }
    return ans;
}
int main()
{
    int s,t;
    n=read(),m=read(),s=read(),t=read();
    while(m--)
    {
        int u=read(),v=read(),w=read(),c=read();
        addedge(u,v,w,c);
    }
    int ans=mcmf(s,t);
    cout<<ans<<" "<<ret<<endl;
}
@gdjcwsk 2020-08-01 22:21 回复 举报

刚看了一下隔壁dalao的代码,感觉没啥可优化的,大家帮我一下吧

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。