2WA求助
查看原帖
2WA求助
71663
lihaoyuan楼主2023/11/15 14:14

学算法的时候就在想,既然不能更改,那这条路是不是可以直接删除。所以我在代码中直接将使用过的和不能使用的删除了,那么理论来讲时间复杂度是O(e)。但是,竟出俩WA。 求助大佬

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int n,m,e;
vector<deque<int>> vec;
vector<int> road,_road;
bool changed(int u){
    while(vec[u].size()){
        int v=vec[u].front();
        vec[u].pop_front();
        if(_road[v])
            if(!changed(_road[v]))
                continue;
        _road[v]=u;
        return 1;
    }
    return 0;
}
int main()
{
    cin>>n>>m>>e;
    vector<vector<bool>> mp(n+1,vector<bool>(m+1,0));
    vec=vector<deque<int>>(n+1);
    //road=vector<int>(n+1);
    _road=vector<int>(m+1,0);
    while(e--)
    {
        int u,v;
        cin>>u>>v;
        mp[u][v]=1;
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(mp[i][j])vec[i].emplace_back(j);
    int ans=0;
    for(int i=1;i<=n;i++){
        if(changed(i))ans++;
    }

    cout << ans << endl;
    return 0;
}
### ```
2023/11/15 14:14
加载中...