ACM 的一道题提交总是Time Limit Exceeded,求救

2025-03-07 03:29:29
推荐回答(1个)
回答1:

你是怎么做的? 二分图的多重匹配这题,如果暴力做的话会T的
代码附一个吧:
#include
#include
#include
using namespace std;
const int N=100010;
int n,m;
int cap[11],map[N][11];
int val[11],mat[11][N];
int mark[11];
bool dfs(int x)
{
for(int i=0;i {
if(!mark[i]&&map[x][i])
{
mark[i]=1;
if(val[i] {
mat[i][val[i]++]=x;
return true;
}
else
for(int j=0;j {
if(dfs(mat[i][j]))
{
mat[i][j]=x;
return true;
}
}
}
}
return false;
}
bool Yes()
{
int i;
memset(val,0,sizeof(val));
for(i=0;i {
memset(mark,false,sizeof(mark));
if(!dfs(i)) return false;
}
return true;
}

int main()
{
while(cin>>n>>m)
{
memset(map,0,sizeof(map));
for(int i=0;i {
for(int j=0;j {
scanf("%d",&map[i][j]);
}
}
for(int i=0;i if(Yes())
printf("YES\n");
else
printf("NO\n");
}
return 0;
}