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:自虐下,最大流算法写错了。。。忘了修改回退边的流量,晕

Posted by yzhw at 2009-05-02 02:48:03 on Problem 1087
In Reply To:求救。。实在找不出错了,还是往死里wa,附代码 Posted by:yzhw9981 at 2009-05-02 02:10:30
> # include <iostream>
> using namespace std;
> # include <set>
> # include <queue>
> # include <string>
> # define MAXNUM 99999999
> struct point
> {
> 	string str;
> 	int id;
> };
> class cmp
> {
> public:
> 	bool operator()(const point &a,const point &b) const
> 	{
> 		return a.str<b.str;
> 	}
> };
> class link
> {
> public:
> 	int c,f;
> 	bool used;
> 	link()
> 	{
> 		used=0;
> 		f=0;
> 	}
> };
> set<point,cmp> refer;
> link g[800][800];
> int vn=0,an=0,c=0,cn,list[1000];
> void dfs(int pos,int level[])
> {
> 	if(pos==c)
> 	{
> 		list[level[pos]]=pos;
> 		int min=MAXNUM;
> 		for(int i=1;i<level[pos];i++)
> 		{
> 			if(g[list[i]][list[i+1]].c&&g[list[i]][list[i+1]].c-g[list[i]][list[i+1]].f<min) 
> 				min=g[list[i]][list[i+1]].c-g[list[i]][list[i+1]].f;
> 			else if(!g[list[i]][list[i+1]].c&&g[list[i]][list[i+1]].f<min) 
> 				min=g[list[i]][list[i+1]].f;
> 		}
> 		for(int i=1;i<level[pos];i++)
> 		{
> 			if(g[list[i]][list[i+1]].c) 
> 				g[list[i]][list[i+1]].f+=min;
> 			else g[list[i]][list[i+1]].f-=min;
> 		}
> 	}
> 	else
> 	{
> 		list[level[pos]]=pos;
> 		for(int i=1;i<=c;i++)
> 		{
> 			if(g[pos][i].used&&level[i]==level[pos]+1&&((g[pos][i].c&&g[pos][i].c-g[pos][i].f>0)||(!g[pos][i].c&&g[pos][i].f)))
> 			{
> 				dfs(i,level);
> 			}
> 		}
> 	}
> }
> 
> void makelevel(int level[])
> {
> 	queue<int> q;
> 	level[c-1]=1;
> 	q.push(c-1);
> 	while(!q.empty())
> 	{
> 		int pos=q.front();
> 		q.pop();
> 		if(pos==c) break;
> 		for(int i=1;i<=c;i++)
> 			if(g[pos][i].used&&(!level[i]||level[i]>level[pos]+1)&&((g[pos][i].c&&g[pos][i].c-g[pos][i].f>0)||(!g[pos][i].c&&g[pos][i].f)))
> 			{
> 				level[i]=level[pos]+1;
> 				q.push(i);
> 			}
> 	}
> }
> int maxflow()//dicnic max-flow algorithm
> {
> 	int level[800];
> 	memset(level,0,sizeof(level));
> 	makelevel(level);
>     while(level[c])
> 	{
> 		dfs(c-1,level);
> 		memset(level,0,sizeof(level));
> 		makelevel(level);
> 	}
> 	int total=0;
> 	for(int i=1;i<=c;i++) if(g[c-1][i].used) total+=g[c-1][i].f;
> 	return total;
> }
> 
> inline void add(int s,int e,int limit)
> {
> 	g[s][e].c=limit;
> 	g[s][e].f=0;
> 	g[e][s].f=0;
> 	g[e][s].c=0;
> 	g[s][e].used=g[e][s].used=1;
> }
> int main()
> {
> 	cin>>vn;
> 	int vnum[101];
> 	memset(vnum,0,sizeof(vnum));
> 	for(int i=1;i<=vn;i++)
> 	{
> 		point temp;
> 		cin>>temp.str;
> 		set<point,cmp>::iterator it=refer.find(temp);
> 		if(it==refer.end())
> 		{
> 			temp.id=++c;
> 			refer.insert(temp);
> 			vnum[c]++;
> 		}
> 		else //去重
> 		{
> 			vn--;
> 			i--;
> 			vnum[it->id]++;
> 		}
> 	}
> 	string t1[101],t2[101];
> 	cin>>an;
> 	int total=an;
> 	int anum[101];
> 	memset(anum,0,sizeof(anum));
> 	for(int i=1;i<=an;i++)
> 	{
> 		cin>>t1[i]>>t2[i];
> 		point temp;
> 		temp.str=t1[i];
> 		set<point,cmp>::iterator it=refer.find(temp);
> 		if(it==refer.end())
> 		{
> 			temp.id=++c;
> 			refer.insert(temp);
> 			anum[c-vn]++;
> 			
> 		}
> 		else
> 		{
> 			anum[it->id-vn]++;
> 			i--;
> 			an--;
> 		}
> 	}
> 	for(int i=1;i<=an;i++)
> 	{
> 		int s=vn+i,e;
> 		point temp;
> 		temp.str=t2[i];
> 		set<point,cmp>::iterator it=refer.find(temp);
> 		if(it==refer.end())
> 		{
> 			temp.id=++c;
> 			e=c;
> 			refer.insert(temp);
> 		}
> 		else e=it->id;
> 		add(s,e,MAXNUM);
> 	}
> 	cin>>cn;
> 	for(int i=1;i<=cn;i++)
> 	{
> 		point temp1,temp2;
> 		int s,e;
> 		cin>>temp1.str>>temp2.str;
> 		set<point,cmp>::iterator it1=refer.find(temp1),it2=refer.find(temp2);
> 		if(it1==refer.end())
> 		{
> 			temp1.id=++c;
> 			s=c;
> 			refer.insert(temp1);
> 		}
> 		else s=it1->id;
> 		if(it2==refer.end())
> 		{
> 			temp2.id=++c;
> 			e=c;
> 			refer.insert(temp2);
> 		}
> 		else e=it2->id;
> 		add(s,e,MAXNUM);
> 	}
> 	c++;
> 	for(int i=vn+1;i<=vn+an;i++)
> 	{
> 		add(c,i,anum[i-vn]);
> 	}
> 	c++;
> 	for(int i=1;i<=vn;i++)
> 	{
> 		add(i,c,vnum[i]);
> 	}
> 	cout<<total-maxflow()<<endl;
> 	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