菜鸡求助,只 A 了两个点
查看原帖
菜鸡求助,只 A 了两个点
180720
oistr楼主2020/9/18 22:23

只过了 #1,#3,似乎那两个点还是样例

搞的我看起来跟在面向样例编程似的

我用邻接表、邻接矩阵都写了一遍,第二个点总是少输出一个。

以下是邻接表和邻接矩阵的代码,邻接表版本加了对重边的判断(难道我判重写错了?),对着题解和教练给的代码查过一遍,并没有感觉哪里出了错。求打我脸(雾

#include <iostream>
#include <cstdio>
using namespace std;

template<typename T>/*T: integer type*/
inline void read(T& num)
{
	char ch;int f;num=0;while(1){ch=getchar();if(ch=='-' || (ch>='0'&&ch<='9')) break;} (ch=='-')?(f=-1):(f=1,num+=ch-'0');while(1){ch=getchar();if(!(ch=='-' || (ch>='0'&&ch<='9'))) break; num*=10;num+=ch-'0';} num*=f;
}

inline void readUseless()
{
	char ch;int f;int num=0;while(1){ch=getchar();if(ch=='-' || (ch>='0'&&ch<='9')) break;} (ch=='-')?(f=-1):(f=1,num+=ch-'0');while(1){ch=getchar();if(!(ch=='-' || (ch>='0'&&ch<='9'))) break; num*=10;num+=ch-'0';} num*=f;
}

struct Node
{
	int first;
};
Node node[1005];
int n;

struct Edge
{
	int v;
	int next;
};
Edge edge[50005]; 
int tot;
void addEdge(int u,int v)
{
	edge[++tot].v=v;
	edge[tot].next=node[u].first;
	node[u].first=tot;
}

int matchx[1005],matchy[1005];

bool vis[1005];
bool agmPath(int u)
{
	for(int e=node[u].first;e;e=edge[e].next)
	{
		int v=edge[e].v;
		if(vis[v]){continue;}
		vis[v]=true;
		if((!matchy[v]) || agmPath(v))
		{
			matchx[u]=v;
			matchy[v]=u;
			return true;
		}
	}
	return false;
}

int hungarian()
{
	int res=0;
	for(int i=1;i<=n;i++)
	{
		if((!matchx[i]) && agmPath(i)){res++;}
	}
	return res;
}

bool added[1005][1005]; 
int main()
{
	int e;
	read(n); readUseless(); read(e);
	int u,v;
	for(int i=1;i<=e;i++)
	{
		read(u); read(v);
		if(!added[u][v])
		{
			added[u][v]=true;
			addEdge(u,v);
		}
	}
	cout<<hungarian()<<endl;
	return 0;
}
#include <iostream>
#include <cstdio>
using namespace std;

template<typename T>/*T: integer type*/
inline void read(T& num)
{
	char ch;int f;num=0;while(1){ch=getchar();if(ch=='-' || (ch>='0'&&ch<='9')) break;} (ch=='-')?(f=-1):(f=1,num+=ch-'0');while(1){ch=getchar();if(!(ch=='-' || (ch>='0'&&ch<='9'))) break; num*=10;num+=ch-'0';} num*=f;
}

struct Node
{
	int first;
};
Node node[1005];
int n;

bool edge[1005][1005];
int m;
inline void addEdge(int u,int v){edge[u][v]=true;}

int matchx[1005],matchy[1005];

bool vis[1005];
bool agmPath(int u)
{
	for(int v=1;v<=m;v++)
	{
		if((!edge[u][v]) || vis[v]){continue;}
		vis[v]=true;
		if((!matchy[v]) || agmPath(v))
		{
			matchx[u]=v;
			matchy[v]=u;
			return true;
		}
	}
	return false;
}

int hungarian()
{
	int res=0;
	for(int i=1;i<=n;i++)
	{
		if((!matchx[i]) && agmPath(i)){res++;}
	}
	return res;
}
 
int main()
{
	int e;
	read(n); read(m); read(e);
	int u,v;
	for(int i=1;i<=e;i++)
	{
		read(u); read(v);
		addEdge(u,v);
	}
	cout<<hungarian()<<endl;
	return 0;
}

(已经把前面冗长的宏定义去掉了,反正这两份代码里也没用到)

2020/9/18 22:23
加载中...