好最小覆盖问题610bicov.cpp

设计一个算法

#include <fstream>
#include <iostream>
#include <math.h>
using namespace std;
ifstream in("input.txt");
ofstream out("output.txt");
int fit=0;	
int t=0;	
int s=0;
class Node
{
	friend class Qunue;
	friend class List;
	friend class Iterator;
	private:
		int data;
		Node *next;
};
class List                           //建立一个链表
{
   friend class Linkbase;
   friend class Iterator;
   public:
	   List(){first=0;}
	   ~List();
	   bool Empty(){return first==0; }
	   int Length();
	   int Retrieve(int k,int x);
	   int Locate(int x);
	   List &Insert(int k,int x);
	   List &Delete(int x);
   private:
	   Node *first;
};

List::~List()
{
	Node *next;
	while(first)
	{
		next=first->next;
		delete first;
		first=next;
	}
}

int List::Length()
{
	Node *now=first;
	int n=0;
	while(now)
	{
		now=now->next;
		n++;
	}
	return n;
}
int List::Retrieve(int k,int x)
{
	if(k<1) return 0;
	Node *p=first;
	int fig=1;
	while(fig<k&&p)
	{
		p=p->next;
		fig++;
	}
	if(p){
		x=p->data;
		return x; }
	return 0;
}
int List::Locate(int x)
{
	Node *p=first;
	int fig=1;
	while(p->data!=x&&p)
	{
		p=p->next;
		fig++;
	}
	if(p)
		return fig;
	return 0;
}
List &List::Insert(int k,int x)
{
	if(k<0) return *this;

	Node *p=first;
	int fig=1;
	for(int i=fig;i<k&&p;i++)
		p=p->next;
	Node *y=new Node;
	y->data=x;
	if(k)
	{
			y->next=p->next;
			p->next=y;	
	}
	else
	{
			y->next=first;
			first=y;
	}
		return *this;
}
List &List::Delete(int x)
{
	Node *p=first,*trail=0;
	while(p&&p->data!=x)
	{
		trail=p;
		p=p->next;
	}
	if(trail)
		trail->next=p->next;
	else
		first=p->next;
	delete p;
	return *this;
}
class Linkbase
{
	friend class Linkgraph;
public:
	Linkbase(int Vertices)
	{  n=Vertices;
	   e=0;
	   h=new List[n+1];
	}
	~Linkbase(){delete[]h;}
	int Edges()const {return e;}
	int Vertices()const {return n;}
	int Outdegree(int i)
	{	return h[i].Length(); }
private:
	int n;
	int e;
	List *h;
};
class Linkgraph:public Linkbase
{
public:
	Linkgraph(int Vertices):Linkbase(Vertices){};
	bool Exist(int i,int j) const;
	Linkgraph &Add(int i,int j);
	Linkgraph &Delete(int i,int j);
    int Findbest(int m1,int m2,int k,int reach1[],int reach2[]);
private:
	Linkgraph &Addnocheck(int i,int j);
	Iterator *pos;
};
bool Linkgraph::Exist(int i,int j)const
{
	return (h[i].Locate(j))?true:false;
}
Linkgraph &Linkgraph::Add(int i,int j)
{
	return Addnocheck(i,j);
}
Linkgraph &Linkgraph::Addnocheck(int i,int j)
{
	h[i].Insert(0,j);
	return *this;
}
Linkgraph &Linkgraph::Delete(int i,int j)
{
	h[i].Delete(j);
	h[j].Delete(i);
	e-=2;
	return *this;
}
int Linkgraph::Findbest(int m1,int m2,int k,int reach1[],int reach2[])
{
	int x;
	for(int i=1;i<=m1;i++)
	{
		if(reach1[i]>1)
		{
			x=h[i].Retrieve(1,x);
			for(int tt=2;x!=0&&reach1[i]>1;)
			{
			
				if(reach2[x]>1)
				{
					--reach2[x];
					--reach1[i];
					k--;
				}
				x=h[i].Retrieve(tt,x);
				tt++;
			}
		}
	}
	return k;
}
main()
{
	int m1,m2,m,k,x,y,i,kk1,kk2;
	in>>m1>>m2>>k;
	if(m1>m2)
		m=m1;
	else m=m2;
	Linkgraph g1(m1);
	Linkgraph g2(m2);
	int *reach1=new int[m1];
	int *reach2=new int[m2];
	int *reach3=new int[m1];
	int *reach4=new int[m2];
	for(i=1;i<=m1;i++)
		reach1[i]=0;
	for(i=1;i<=m2;i++)
		reach2[i]=0;
	for(i=1;i<=m1;i++)
		reach3[i]=0;
	for(i=1;i<=m2;i++)
		reach4[i]=0;
	{
		{
			for(i=0;i<=k-1;i++)
			{in>>x>>y;
			g1.Add(x,y);
			g2.Add(y,x);
			reach1[x]++;
			reach2[y]++;
			reach3[x]++;
			reach4[y]++;
			}
		}	

	}
	kk1=g1.Findbest(m1,m2,k,reach1,reach2);
	kk2=g2.Findbest(m2,m1,k,reach4,reach3);
	if(kk1<kk2)
		out<<kk1;
	else out<<kk2<<endl;
	return 0;
}