Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:求指教。。为什么我的代码把maxn .maxm调的很高才能过?In Reply To:求指教。。为什么我的代码把maxn .maxm调的很高才能过? Posted by:ssdut_201392326 at 2014-08-11 11:20:44 泥错了,关键不是maxn而是maxm,maxn最大100,开100+足够了啊,,但是maxm也就是边数题目不是说了<=n^2(也就是10000+)么... 然后泥的算法显然是加了反向边的(要两倍),并且源点到各个power station,以及slinks到汇点都是要额外加边的,那么至少也要20100+吧... > maxn = 1000,maxm = 20050 一直RE。 > 看了discuss,干脆丧心病狂改成很大的了。。然后才过,为什么这题maxn开到1000都不够??费解。。。 > > > #include<cstdio> > #include<cstring> > #include<iostream> > using namespace std; > const int maxn = 100000; > const int maxm = 200500; > const int INF = 0x7FFFFFF; > #define mem(name,value) memset((name),(value),sizeof(name)) > struct Side{ > int to,next,c; > }side[maxm]; > int top,node[maxn]; > void add_side(int u,int v,int c,int rc){ > side[top]=(Side){v,node[u],c};node[u]=top++; > side[top]=(Side){u,node[v],rc};node[v]=top++; > } > int start,end,cnt,dis[maxn],gap[maxn]; > int get_flow(int u,int flow){ > //printf("%d %d\n",u,flow); > if(u==end)return flow; > int ans=0; > for(int i=node[u];i!=-1;i=side[i].next){ > int v=side[i].to,c=side[i].c; > if(dis[u]>dis[v]&&c){ > int f=get_flow(v,min(flow-ans,c)); > ans+=f; > side[i].c-=f; > side[i^1].c+=f; > if(ans==flow)return ans; > } > } > if(!(--gap[dis[u]]))dis[start]=cnt+2; > gap[++dis[u]]++; > return ans; > } > int main(){ > freopen("input.txt","r",stdin); > int n,np,nc,m; > while(scanf("%d%d%d%d",&n,&np,&nc,&m) != EOF){ > top=0; > mem(node,-1); > mem(gap,0); > mem(dis,0); > while(m--){ > int u,v,w; > char str[20]; > scanf("%s",str); > sscanf(str,"(%d,%d)%d",&u,&v,&w); > //cout<<u<<" "<<v<<" "<<w<<endl; > add_side(u,v,w,0); > } > while(np--) > { > int u = n+1,v,w; > char str[20]; > scanf("%s",str); > sscanf(str,"(%d)%d",&v,&w); > //cout<<u<<" "<<v<<" "<<w<<endl; > add_side(u,v,w,0); > } > while(nc--) > { > int u,v = n+2,w; > char str[20]; > scanf("%s",str); > sscanf(str,"(%d)%d",&u,&w); > //cout<<u<<" "<<v<<" "<<w<<endl; > add_side(u,v,w,0); > } > if(np==0 || nc==0){cout<<0<<endl; continue;} > int ans=0; > start=n+1; > end=n+2; > cnt=n+2; > gap[0]=cnt; > while(dis[start]<cnt)ans+=get_flow(start,INF); > printf("%d\n",ans); > } > return 0; > } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator