Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:求指教。。为什么我的代码把maxn .maxm调的很高才能过?

Posted by 3013216027 at 2015-05-01 10:47:34 on Problem 1459 and last updated at 2015-05-01 10:48:38
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator