1083 - Fare and Balanced

All about problems in Volume 10. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
fsps60312
New poster
Posts: 16
Joined: Sun Jan 25, 2015 5:46 pm

Re: 1083 - Fare and Balanced

Post by fsps60312 » Wed Feb 18, 2015 4:50 pm

Why WA :( ?
Here is my idea:
for each road, calculate the max(stored in EDGE.lsum) & min(stored in EDGE.ssum) length of path pass by this road(stored in EDGE.sum)
for each road intersection that has no road enter, use dfs to traval through the graph, if encounter a road that lsum==ssum, then add the road number & toll to ANS, and return
if there is a way that for every road on the way, none has lsum==ssum, then output "No solution"
But I just can't figure out where I'm wrong.
Or is there crutial testcases missed? Please help me!
Any reply will be appreciated.
This is my code:

Code: Select all

#include<cstdio>
#include<cstdlib>
#include<vector>
#define min(x,y) (x)<(y)?(x):(y)
#define max(x,y) (x)>(y)?(x):(y)
using namespace std;
int N,M,VIS[50001],IN[50001],OUT[50001],MAX;
struct Pair
{
	int x,y;
	Pair operator+(int a){return (Pair){x+a,y+a};}
};
struct Edge
{
	int from,to,val,lsum,ssum;
	Pair down,up;
	void init(int f,int t,int v){from=f,to=t,val=v;}
	bool allthesame(){return down.x+up.x==down.y+up.y;}
};
vector<Edge> EDGE;
vector<int> TO[50001],FROM[50001];
Pair dfsdown(int u,int val)
{
	Pair &ans=EDGE[u].down;
	if(VIS[u])return ans+val;
	VIS[u]=1;
	int to=EDGE[u].to;
	ans=(Pair){EDGE[u].val,EDGE[u].val};
	if(!TO[to].size())return ans+val;
	ans=dfsdown(TO[to][0],EDGE[u].val);
	for(int i=1;i<TO[to].size();i++)
	{
		int idx=TO[to][i];
		Pair p=dfsdown(idx,val+EDGE[u].val);
		ans.x=min(ans.x,p.x-val);
		ans.y=max(ans.y,p.y-val);
	}
	return ans+val;
}
Pair dfsup(int u,int val)
{
	Pair &ans=EDGE[u].up;
	if(VIS[u])return ans+val;
	VIS[u]=1;
	int from=EDGE[u].from;
	ans=(Pair){EDGE[u].val,EDGE[u].val};
	if(!FROM[from].size())return ans+val;
	ans=dfsup(FROM[from][0],EDGE[u].val);
	for(int i=0;i<FROM[from].size();i++)
	{
		int idx=FROM[from][i];
		Pair p=dfsup(idx,val+EDGE[u].val);
		ans.x=min(ans.x,p.x-val);
		ans.y=max(ans.y,p.y-val);
	}
	return ans+val;
}
vector<Pair> ANS;
bool dfsans(int u)
{
	//printf("u=%d,(%d,%d)\n",u,EDGE[u].ssum,EDGE[u].lsum);
	if(VIS[u])return true;
	VIS[u]=1;
	if(EDGE[u].ssum==EDGE[u].lsum)
	{
		if(MAX==EDGE[u].lsum)return true;
		ANS.push_back((Pair){u+1,MAX-EDGE[u].lsum});
		for(int i=ANS.size()-1;i>0;i--)
		{
			Pair &a=ANS[i],&b=ANS[i-1];
			if(a.x>b.x)break;
			Pair t=a;
			a=b;
			b=t;
		}
		return true;
	}
	int to=EDGE[u].to;
	if(!OUT[to])return false;
	for(int i=0;i<TO[to].size();i++)
	{
		int idx=TO[to][i];
		if(!dfsans(idx))return false;
	}
	return true;
}
void solve()
{
	ANS.clear();
	for(int i=0;i<M;i++)VIS[i]=0;
	for(int i=0;i<M;i++)
	{
		if(IN[EDGE[i].from])continue;
		if(!dfsans(i))
		{
			printf(" No solution\n");
			return;
		}
	}
	printf(" %d %d\n",ANS.size(),MAX);
	for(int i=0;i<ANS.size();i++)printf("%d %d\n",ANS[i].x,ANS[i].y);
}
int main()
{
	//freopen("in.txt","r",stdin);
	int kase=1;
	while(scanf("%d%d",&N,&M)==2&&(N||M))
	{
		EDGE.clear();
		for(int i=1;i<=N;i++)
		{
			TO[i].clear();
			FROM[i].clear();
			IN[i]=OUT[i]=0;
		}
		for(int i=0;i<M;i++)
		{
			int a,b,val;scanf("%d%d%d",&a,&b,&val);
			Edge e;
			e.init(a,b,val);
			EDGE.push_back(e);
			TO[a].push_back(i);
			FROM[b].push_back(i);
			IN[b]++,OUT[a]++;
		}
		for(int i=0;i<M;i++)VIS[i]=0;
		for(int i=0;i<M;i++)if(!IN[i])
		{
			for(int ti=0;ti<TO[i].size();ti++)
			dfsdown(TO[i][ti],0);
		}
		for(int i=0;i<M;i++)VIS[i]=0;
		for(int i=0;i<M;i++)if(!OUT[i])
		{
			for(int ti=0;ti<FROM[i].size();ti++)
			dfsup(FROM[i][ti],0);
		}
		MAX=0;
		for(int i=0;i<M;i++)
		{
			EDGE[i].ssum=EDGE[i].up.x+EDGE[i].down.x-EDGE[i].val;
			EDGE[i].lsum=EDGE[i].up.y+EDGE[i].down.y-EDGE[i].val;
			MAX=max(MAX,EDGE[i].lsum);
		}
		printf("Case %d:",kase++);
		/*for(int i=0;i<M;i++)
		{
			Pair down=EDGE[i].down,up=EDGE[i].up;
			printf("%d:%d->%d\t%d,%d\t%d,%d\n",i+1,EDGE[i].from,EDGE[i].to,down.x,down.y,up.x,up.y);
		}*/
		solve();
	}
	return 0;
}

tosinosu
New poster
Posts: 1
Joined: Fri Jul 01, 2016 1:56 pm

Re: 1083 - Fare and Balanced

Post by tosinosu » Fri Jul 01, 2016 2:08 pm

can somebody please put comments on these lines of codes.

Post Reply

Return to “Volume 10 (1000-1099)”