只过了 #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;
}
(已经把前面冗长的宏定义去掉了,反正这两份代码里也没用到)