Znzryb's Blog
0%

Posted on Edited on

题目大意

给定多组数据。每组有 nn 个物品，每个物品有两个值 AiA_i、BiB_i，需要选出恰好 kk 个物品，使得 max⁡(A)\max(A) 与所选 BB 的和构成的目标值最小（题目要求输出该最小值）。

AC代码

总体思路就是A的值只由最大Ar决定，那么其他值怎么填那？自然是使他们的B值总和最小

然后记得sumB要归0。

AC https://atcoder.jp/contests/abc376/submissions/59002823

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <iostream>
#include <cstring>
#include <cmath>
#include <vector>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll N=2e5+10;
ll n,k,T,ans,B[N],sumB;
pair<ll,ll> A[N];
// struct comp {
//     bool operator()(ll a,ll b) {
//         if(B[a]!=B[b]) {
//             return B[a]<B[b];
//         }
//         return false;
//     }
// };
priority_queue<ll> pq;
bool cmp(pair<ll,ll> a,pair<ll,ll> b) {
    if(a.first!=b.first)
        return a.first<b.first;
    return false;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>T;
    for(int _=1;_<=T;++_) {
        cin>>n>>k;
        priority_queue<ll> empty;
        swap(pq,empty);     // 模拟clear操作
        ans=1e18+7;sumB=0;
        for(int i=1;i<=n;++i) {
            ll ae;
            cin>>ae;
            A[i]=make_pair(ae,i);
        }
        for(int i=1;i<=n;++i) {
            cin>>B[i];
        }
        sort(&A[1],&A[n+1],cmp);
        for(int i=1;i<=k;++i) {
            sumB+=B[A[i].second];
            pq.push(B[A[i].second]);
        }
        ans=sumB*A[k].first;
        for(int i=k+1;i<=n;++i) {
            sumB-=pq.top();
            sumB+=B[A[i].second];
            pq.pop();
            pq.push(B[A[i].second]);
            ans=min(ans,sumB*A[i].first);
        }
        cout<<ans<<endl;
    }
    return 0;
}
// AC https://atcoder.jp/contests/abc376/submissions/59002823

心路历程（WA，TLE，MLE……）

Posted on Edited on

shift+command+/ 表示/。。。/

Posted on Edited on

题目大意

给定一个二分图，左部点集大小 n，右部点集大小 m，边集大小 e。求该二分图的最大匹配数（即最多的边数，使得这些边没有任何公共端点）。

AC代码

增广路的神奇之处在于，如果我们沿着一条增广路，将路径上的非匹配边变成匹配边，同时将匹配边变成非匹配边，那么匹配边的总数就会增加 1。

举个例子：

假设我们有下面这条增广路（实线代表匹配边，虚线代表非匹配边）：

未匹配点1 --(虚线)--> 点A ==(实线)== 点B --(虚线)--> 未匹配点2

  • 这条路径从一个未匹配点开始，到一个未匹配点结束。

  • 路径上的边是“非匹配-匹配-非匹配”交替的。

如果我们对它进行“增广”操作（虚实互换）：

未匹配点1 ==(实线)== 点A --(虚线)-- 点B ==(实线)== 未匹配点2

看！原来的 1 条匹配边（A-B）现在变成了 2 条（点1-A，B-点2）。匹配的总数增加了！

一个重要的结论是：一个匹配是最大匹配，当且仅当图中不存在增广路。 这也构成了匈牙利算法的理论基础。

视频教程

https://www.acwing.com/video/290/

匈牙利算法精髓：

👉 Note: 姑娘 j （connectedr）遇到新的追求者的心理活动：如果原来的男朋友有备胎，我就绿他，如果没有，那我看他太可怜了，就一直跟他在一起吧。

还有一个要注意的地方就是vis数组每次都要清空，因为实际上记的是这次寻找有没有找过这个宠物，这是为了防止死循环的发生（爆栈）

AC https://www.luogu.com.cn/record/183163854

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
// https://www.luogu.com.cn/problem/P3386
// https://www.acwing.com/problem/content/863/
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
const ll N=510;
ll n,m,u,v,e,ans;
vector<ll> g[N],r[N];
bool vis[N];
ll matchr[N];
bool find(ll i) {
    for(int j=0;j<g[i].size();j++) {
        ll connectedr=g[i][j];
        if(vis[connectedr])
            continue;
        vis[connectedr]=true;
        if(matchr[connectedr]==0 || find(matchr[connectedr]) ) {
            matchr[connectedr]=i;
            return true;
        }
    }
    return false;
}
int main()
{
    cin>>n>>m>>e;
    for(int i=1;i<=e;i++) {
        cin>>u>>v;
        // if(removeSame[u][v])
        //     continue;
        // removeSame[u][v]=true;
        g[u].push_back(v);
    }
    for(int i=1;i<=n;i++) {
        fill(&vis[0],&vis[n+1],false);
        if(find(i))
            ++ans;
    }
    cout<<ans<<endl;
    return 0;
}

// 70 pts https://www.luogu.com.cn/record/183070840
// 80 pts https://www.luogu.com.cn/record/183076675
// AC https://www.luogu.com.cn/record/183163854

心路历程（WA，TLE，MLE……）

好像有点问题，但问题不大，过了70pts

https://www.luogu.com.cn/record/183070840

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
// https://www.luogu.com.cn/problem/P3386
// https://www.acwing.com/problem/content/863/
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
const ll N=510;
ll n,m,u,v,e,ans;
vector<ll> l[N],r[N];
bool removeSame[N][N];
ll matchr[N],sl[N];     // sl为左边点的起始索引记录
inline void Hungarian(){    // 匈牙利算法
    for(int i=1;i<=n;i++) {
        if(l[i].empty())
            continue;
        if(matchr[l[i][0]]==0) {
            matchr[l[i][0]]=i;
            ++sl[i];++ans;
        }else {
            ll originMatch=matchr[l[i][0]];bool isBreak=false;
            for(ll j=sl[originMatch];j<l[originMatch].size();j++) {
                ll rConnected=l[originMatch][j];
                if(matchr[rConnected]==0) {
                    matchr[rConnected]=originMatch;
                    sl[originMatch]=j+1;isBreak=true;       // 只是换了一下配对关系，无需++ans
                    break;
                }
            }
            if(isBreak) {
                matchr[l[i][0]]=i;
                ++sl[i];
                ++ans;
            }
        }
    }
}
int main()
{
    cin>>n>>m>>e;
    for(int i=1;i<=e;i++) {
        cin>>u>>v;
        // if(removeSame[u][v])
        //     continue;
        // removeSame[u][v]=true;
        l[u].push_back(v);
        r[v].push_back(u);
    }
    Hungarian();
    cout<<ans<<endl;
    return 0;
}

// 70 pts https://www.luogu.com.cn/record/183070840

80pts https://www.luogu.com.cn/record/183076675

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
// https://www.luogu.com.cn/problem/P3386
// https://www.acwing.com/problem/content/863/
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
const ll N=510;
ll n,m,u,v,e,ans;
vector<ll> g[N],r[N];
bool removeSame[N][N];
ll matchr[N],sl[N];     // sl为左边点的起始索引记录
inline void Hungarian(){    // 匈牙利算法
    for(int i=1;i<=n;i++) {
        if(g[i].empty())
            continue;
        if(matchr[g[i][0]]==0) {
            matchr[g[i][0]]=i;
            ++sl[i];++ans;
        }else {
            for(int k=0;k<g[i].size();k++) {
                ll originMatch=matchr[g[i][k]];bool isBreak=false;
                for(ll j=sl[originMatch];j<g[originMatch].size();j++) {
                    ll rConnected=g[originMatch][j];
                    if(matchr[rConnected]==0) {
                        matchr[rConnected]=originMatch;
                        sl[originMatch]=j+1;isBreak=true;       // 只是换了一下配对关系，无需++ans
                        break;
                    }
                }
                if(isBreak) {
                    matchr[g[i][0]]=i;
                    ++sl[i];
                    ++ans;
                    break;
                }
            }
        }
    }
}
int main()
{
    cin>>n>>m>>e;
    for(int i=1;i<=e;i++) {
        cin>>u>>v;
        // if(removeSame[u][v])
        //     continue;
        // removeSame[u][v]=true;
        g[u].push_back(v);
    }
    Hungarian();
    cout<<ans<<endl;
    return 0;
}

// 70 pts https://www.luogu.com.cn/record/183070840
// 80 pts https://www.luogu.com.cn/record/183076675

用循环是解决不了的，还是要递归。

Posted on Edited on

题目大意

给定一个无向图，判断该图是否为二分图（即是否能将所有点分成两个集合，使得所有边都只连接不同集合的点）。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
const ll N=1e5+10;
ll n,m,u,v;
short int color[N];
vector<ll> g[N];
bool isErfen=true;
void dfs(int x,int c) {
    if(isErfen==false)
        return;
    if(color[x]==0)
        color[x]=c;
    else {
        if(color[x]!=c) {
            isErfen=false;
            return;
        }
        return;
    }
    for(int i=0;i<g[x].size();i++) {
        dfs(g[x][i],3-c);       // 小的一个trick
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++) {
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for(int i=1;i<=n;i++) {
        if(color[i]==0)
            dfs(i,1);
        if(isErfen==false)
            break;
    }
    if(isErfen)
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;
}
// AC https://www.acwing.com/problem/content/submission/code_detail/37509674/