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:自虐下,最大流算法写错了。。。忘了修改回退边的流量,晕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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator