| ||||||||||
| 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