round1 传纸条 本地AC 提交WA

#include<iostream>
#include<cstdio>
#include<cstring>
#include<deque>
using namespace std;
const int MAXN=6233,MAXM=233333,SHIFT=3000;
struct edge
{
    int v,f,w;
    edge *next,*rev;
}*h[MAXN],pool[MAXM*2];
int top;
inline void addedge(int u,int v,int c,int w)
{
    //cout<<"ADDEDGE"<<u<<' '<<v<<' '<<c<<' '<<w<<",top="<<top<<endl;
    edge *tmp=&pool[top++];tmp->v=v;tmp->f=c;tmp->w=w;tmp->next=h[u];h[u]=tmp;
    edge *pmt=&pool[top++];pmt->v=u;pmt->f=0;pmt->w=-w;pmt->next=h[v];h[v]=pmt;
    tmp->rev=pmt;pmt->rev=tmp;
}
inline int Hash(int i,int j){return (i-1)*50+j-1;}
deque<int> q;
int S,T;
int last[MAXN],inq[MAXN];
long long dis[MAXN],maxf[MAXN];
edge *laste[MAXN];
long long totcost,totflow;
bool SPFA()
{
    //cout<<"SPFA"<<endl;
    memset(dis,0x3f,sizeof(dis));
    memset(last,0,sizeof(last));
    memset(maxf,0,sizeof(maxf));
    memset(inq,0,sizeof(inq));
    while(!q.empty())q.pop_front();
    q.push_front(S);
    maxf[S]=0x3f3f3f3f3f3f3f3fll;
    inq[S]=1;
    dis[S]=0;
    while(!q.empty())
    {
        int u=q.front();q.pop_front();
        inq[u]=0;
        //cout<<"SPFA("<<u<<",dis = "<<dis[u]<<",maxFlow = "<<maxf[u]<<",last = "<<last[u]<<")\n";
        for(edge *tmp=h[u];tmp;tmp=tmp->next)
        {
            if(tmp->f&&dis[tmp->v]>dis[u]+tmp->w)
            {
                dis[tmp->v]=dis[u]+tmp->w;
                last[tmp->v]=u;
                maxf[tmp->v]=max(maxf[tmp->v],min(maxf[u],(long long)tmp->f));
                laste[tmp->v]=tmp;
                if(!inq[tmp->v])
                {
                    if(q.empty()||dis[q.front()]>tmp->v)q.push_front(tmp->v);
                    else q.push_back(tmp->v);
                    inq[tmp->v]=1;
                }
            }
        }
    }
    if(dis[T]>=0x3f3f3f3f3f3f3f3fll)return false;
    int u=T;
    while(last[u])
    {
        //cout<<u<<endl;
        laste[u]->f-=maxf[T];
        laste[u]->rev->f+=maxf[T];
        u=last[u];
    }
    totcost+=dis[T]*maxf[T];
    totflow+=maxf[T];
    return true;
}
int n,m;
int mat[55][55];
int main()
{
    scanf("%d%d",&m,&n);//upd:m和n已交换,还是WA。。
    S=Hash(1,1)+SHIFT,T=Hash(m,n);
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            scanf("%d",&mat[i][j]);
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
        {
            if(i!=m)addedge(Hash(i,j)+SHIFT,Hash(i+1,j),1,0);
            if(j!=n)addedge(Hash(i,j)+SHIFT,Hash(i,j+1),1,0);
            addedge(Hash(i,j),Hash(i,j)+SHIFT,1,-mat[i][j]);
        }
    while(SPFA());
    printf("%lld\n",-totcost);
    return 0;
}

QWQ

8 条评论

  • @ 2017-08-21 17:53:37

    严重怀疑数据有问题(

  • @ 2017-08-21 17:53:17

    这个费用流的代码在loj模板题上也是能A的

  • @ 2017-08-21 17:52:21

    我把nm换了还是WA
    在洛谷上交能AC的。。。

  • @ 2017-08-21 10:53:43

    这份标程可过,(网上一大堆cpp代码GG掉了,我交网上code wa了无数次),(最后还是自己努力吧)。
    原因如下:
    1.你的n,m写反了。
    2.......就是写错了吧,不懂

  • @ 2017-08-21 10:44:43
    #include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    int n,m,t,x,y,nu=1,ans;
    int ap[55][55],q[3][3];
    int las[70005],b[70005],nex[70005],f[70005],dis[70005],v[70005],re[70005],a[70005];
    bool bz[70005];
    inline int min(int x,int y){
        return x<y?x:y;
    }
    inline void insert(int x,int y,int z,int k){
        b[++nu]=y;nex[nu]=las[x];las[x]=nu;f[nu]=z;v[nu]=k;
        b[++nu]=x;nex[nu]=las[y];las[y]=nu;f[nu]=0;v[nu]=-k;
    }
    inline void read(int &res){
        static char ch;register int flag=1;
        while((ch=getchar())<'0'||ch>'9')if(ch=='-')flag=-1;res=ch-48;
        while((ch=getchar())>='0'&&ch<='9')res=res*10+ch-48;res*=flag;
    }
    const int INF=0x7fffffff;
    inline bool spfa(){
        register int l=0,r=1,now,p;
        memset(bz,0,sizeof(bz));
        fill(dis,dis+70000,-INF);
        dis[1]=0,a[1]=1;bz[1]=1;
        while(l<r){
            now=a[++l];p=las[now];
            while(p!=0){
                if((dis[b[p]]<dis[now]+v[p])&&f[p]>0){
                    dis[b[p]]=dis[now]+v[p];re[b[p]]=p;
                    if(!bz[b[p]])bz[b[p]]=1,r++,a[r]=b[p];
                }
                p=nex[p];
            }
            bz[now]=0;
        }
        if(dis[t]>0)ans+=dis[t];
        return dis[t]>0;
    }
    inline void find(){
        register int p,x,sum;
        x=t;sum=INF;
        while(x!=1)sum=min(sum,f[re[x]]),x=b[re[x]^1];
        x=t;
        while(x!=1)f[re[x]]-=sum,f[re[x]^1]+=sum,x=b[re[x]^1];
    }
    int main(){
        q[1][2]=q[2][1]=1;
        read(n),read(m),t=n*m*2;
        for(register int i=1;i<=n;i++)
            for(register int j=1;j<=m;j++)
                read(ap[i][j]);
        insert(n*m,n*m*2,2,0),insert(1,n*m+1,2,0);
        for(register int i=1;i<=n;i++)
            for(register int j=1;j<=m;j++){
                for(register int k=1;k<=2;k++){
                    x=i+q[k][1];y=j+q[k][2];
                    if(x<1||y<1||x>n||y>m)continue;
                    insert((i-1)*m+j+n*m,(x-1)*m+y,1,ap[x][y]);
                }
                if(i==1&&j==1)continue;
                if(i==n&&j==m)continue;
                insert((i-1)*m+j,(i-1)*m+j+n*m,1,0);
            }
        while(spfa())find();
        cout<<ans<<endl;
        return 0;
    }
    
    • @ 2017-08-21 10:48:05

      真的无语,一个简单的四维DP,被你们弄的这么复杂

    • @ 2017-08-21 11:28:07

      @蒟蒻noname:反正闲着蛋疼

  • @ 2017-08-21 10:39:46

    我是出题者,我表示很懵逼,测试数据没问题的,读入问题吧

  • @ 2017-08-21 09:59:29

    改了也是错的qaq,我干脆写一份吧

  • @ 2017-08-21 09:59:05

    你m与n的循环与输入不符合i

  • 1