- 问答
- 2017-08-20 17:45:00 @
#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 条评论
-
oscar2001 LV 4 @ 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:39:46@
我是出题者,我表示很懵逼,测试数据没问题的,读入问题吧
-
2017-08-21 09:59:29@
改了也是错的qaq,我干脆写一份吧
-
2017-08-21 09:59:05@
你m与n的循环与输入不符合i
- 1