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