DICNIC写炸了。。。求检查。。。

Arcturus1350 @ 2018-03-13 21:44:35

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m;
int cnt=2;
int alist[6000001];
struct data{
    int v;int next;int value;
}edge[6000001];
void add(int u,int v,int value)
{
    edge[cnt].v=v;
    edge[cnt].value=value;
    edge[cnt].next=alist[u];
    alist[u]=cnt++;
    return ;
}
int h[1000001];
int q[1000001];
bool bfs()
{
    int x,next;
    memset(h,-1,sizeof(h));
    int head=0,tail=1;
    q[head]=1;
    h[1]=0;
    while(head<tail)
    {
        x=q[head++];
        next=alist[x];
        while(next)
        {
            int v=edge[next].v;
            int value=edge[next].value;
            if(value&&h[v]<0)
            {
                q[tail++]=v;
                h[v]=h[x]+1;
            }
            next=edge[next].next;
        }
    }
//    for(int i=1;i<=n*m;i++) printf("h[%d]=%d\n",i,h[i]);
    if(h[m]==-1) return false;
    return true;
}
int ans;
int dfs(int x,int y)
{
    if(x==m) return y;
    int next=alist[x];
    int w,used=0;
    while(next)
    {
        int v=edge[next].v;
        int value=edge[next].value;
        if(value&&h[v]==h[x]+1)
        {
                w=y-used;
                w=dfs(v,min(w,value));
                edge[next].value-=w;
                edge[next^1].value+=w;
                used+=w;
                if(used==y) return y;
        }
        next=edge[next].next;
    }
    if(!used) h[x]=-1;
    return used;
}
void dinic()
{
    while(bfs()) ans+=dfs(1,0x7fffffff);
}
int n1,m1,e1;
int main()
{
    scanf("%d%d%d%d",&n1,&m1,&m,&n);
    for(int i=1;i<=m1;i++)
    {
        int u,v,val;
        scanf("%d%d%d",&u,&v,&val);
        add(u,v,val);
        add(v,u,val);
    }
    dinic();
    printf("%d",ans);
    return 0;
}

by shadowice1984 @ 2018-03-13 21:51:04

dicnic还能写炸？

by BriMon @ 2018-03-13 21:51:48

%%%Orz

by shadowice1984 @ 2018-03-13 21:52:27

struct data{int v;int nxt;int cot;}edge[M];
int alist[N];int cnt=1;int res;
inline void add(int u,int v,int cot)
{
    edge[++cnt].v=v;edge[cnt].nxt=alist[u];alist[u]=cnt;edge[cnt].cot=cot;
    edge[++cnt].v=u;edge[cnt].nxt=alist[v];alist[v]=cnt;edge[cnt].cot=0;
}
int dep[N];queue <int> q;int ctt;int s;int t;
inline bool bfs()
{
    for(int i=1;i<=ctt;i++){dep[i]=0x3f3f3f3f;}
    dep[s]=0;q.push(s);
    while(!q.empty())
    {
        int now=q.front();q.pop();int nxt=alist[now];
        while(nxt)
        {
            int v=edge[nxt].v;int cot=edge[nxt].cot;
            if(dep[v]==0x3f3f3f3f&&cot!=0)
            {dep[v]=dep[now]+1;q.push(v);}
            nxt=edge[nxt].nxt;
        }
    }return dep[t]!=0x3f3f3f3f;
}
inline int dfs(int x,int lim)
{
    if(x==t){return lim;}
    int nxt=alist[x];int nowflow=0;
    while(nxt)
    {
        if(lim==0)break;
        int v=edge[nxt].v;int cot=edge[nxt].cot;
        if(dep[v]==dep[x]+1&&cot!=0)
        {
            int del=dfs(v,min(lim,cot));
            lim-=del;nowflow+=del;
            edge[nxt].cot-=del;edge[nxt^1].cot+=del;
        }nxt=edge[nxt].nxt;
    }if(nowflow==0){dep[x]=0x3f3f3f3f;}
    return nowflow;
}

while(bfs()){res+=dfs(s,0x3f3f3f3f);}

by shadowice1984 @ 2018-03-13 21:52:59

核心代码，拿好不谢233

by 落寞音箫 @ 2018-03-13 21:56:52

写SAP吧，改良后的SAP既短又快。23333

by 落寞音箫 @ 2018-03-13 21:58:45

@cn：苏卿念

inline int sap(int u,int maxflow){
    if(u==ed)return maxflow;
    int addflow=maxflow,f;
    for(re int i=head[u];i;i=edges[i].last){
        int to=edges[i].to;
        if(d[u]==d[to]+1&&edges[i].flow){
            int f=isap(to,Min(addflow,edges[i].flow));
            addflow-=f;
            edges[i].flow-=f;
            edges[i^1].flow+=f;
            if(!addflow)return maxflow;
        }
    }
    if(!--gap[d[u]])d[st]=n;
    ++gap[++d[u]];
    return maxflow-addflow;
}
int main({
    n=read(),m=read(),st=read(),ed=read();
    For(i,1,m)add(read(),read(),read());
    gap[0]=n;
    while(d[st]<n)ans+=isap(st,1e9);
    printf("%d\n",ans);

by sigland @ 2018-03-13 22:14:34

dfs有问题

by 权御天下 @ 2018-03-13 22:25:55

突然想到有大佬发明了20行最大流