8/9 基础思维+二分图染色+最大完美匹配KM算法

二分图判定染色法

大佬链接：https://www.bilibili.com/video/BV1sZ4y1i7NZ?spm_id_from=333.999.0.0&vd_source=91973ada1213cf6ba2cbb43a2bebd2e8

定理:二分图不存在奇环，只存在偶数环

#include
#define int long long
#define endl '\n'

using namespace std;
const int N=5e5+5;
const int inf=0x3f3f3f3f;
int n,m,cnt,head[N],color[N];
struct node
{
    int to,nxt;
}e[N];
void add(int from,int to)
{
    e[++cnt].to=to;
    e[cnt].nxt=head[from];
    head[from]=cnt;
}
bool dfs(int u,int c) //判断是否是二分图
{
    color[u]=c;
    for(int i=head[u];i;i=e[i].to)
    {
        int v=e[i].to;
        if(!color[v])
            if(dfs(v,3-c)) return 1;
        else if(color[v]==c)
            return 1;
    }
    return 0;
}
signed main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int u,v;cin>>u>>v;
        add(u,v),add(v,u);
    }
    int flag=1;
    for(int i=1;i<=n;i++)
        if(!color[i])
        {
            if(dfs(i,1))
            {
                flag=0;
            }
        }
    if(flag)
        cout<<"YES"<<endl;
    else
        cout<<"NO"<<endl;
    return 0;
}

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

D. The Number of Imposters

这题属实把我写烦了，代码怎么调都有问题
技巧：
1.主程序放到函数中，会提高编程效率。本题快了将近400ms。
2.N若是e5次方基本，一般定义为700010便可不用管了。
本题思路：
1.若是骗子，说的话一定说明两人是相反阵营。
2.若是正常队员，说的真话，则说明两人一定处于相同阵营。本题学到了一个建立虚点的技巧：采用一个中间点，来进行同类归并

e[u].push_back(g), e[g].push_back(u);
e[g].push_back(v), e[v].push_back(g);
1
2

3.要求最大的骗子数，那么对于每一次深搜，两个连通块较大的那个设置为骗子阵营。

#include
#define int long long
#define endl '\n'
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
using namespace std;
const int N=700010;
const int inf=0x3f3f3f3f;
int n,m,cnt;
int color[N],mx1,mx2;
vector<int>e[N];
bool dfs(int x, int c)
{
	color[x] = c;
	if (x <= n)
    {
		if (c == 1) mx1++;
		else mx2++;
	}
	for (int j : e[x])
	{
		if (!color[j])
		{
			if (!dfs(j, 3 - c))
                return false;
		}
		else if (color[j] == color[x])
            return false;
	}
	return true;
}
void solve()
{
    cin>>n>>m;
    for(int i=0;i<=n+m;i++) e[i].clear(),color[i]=0;
    int id=n;
    for(int i=1;i<=m;i++)
    {
        int u,v;string s;
        cin>>u>>v>>s;
        if(s=="crewmate")
        {
            int g=++id; //建立虚点
            e[u].push_back(g), e[g].push_back(u);
            e[g].push_back(v), e[v].push_back(g);
        }
        else
            e[u].push_back(v), e[v].push_back(u);
    }
    int flag=1;
    int ans=0;
    for(int i=1;i<=id;i++)
    {
        if(!color[i])
        {
            mx1=mx2=0;
            if(!dfs(i,1))
            {
                cout<<-1<<endl;
                return;
            }
            ans+=max(mx1,mx2);
        }
    }
    cout<<ans<<endl;
}
signed main()
{
    ios;
    int t;cin>>t;
    while(t--)
    {
        solve();
    }
    return 0;
}

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
64
65
66
67
68
69
70
71
72
73
74
75
76

D. The Door Problem

思路：
1.对于一扇门来说，如果本来就是开的，那么控制改灯的两个开关应属于不用阵营；
2.若一扇门本来是关的，那么控制改灯的两个开关应属于统一阵营

#include
#define int long long
#define endl '\n'
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
using namespace std;
const int N=700010;
const int inf=0x3f3f3f3f;
int n,m,a[N];
int color[N],mx1,mx2;
vector<int>q[N];
struct node
{
    int to,nxt,w;
}e[N];
int cnt,head[N];
void add(int from,int to,int w)
{
    e[++cnt].to=to;
    e[cnt].w=w;
    e[cnt].nxt=head[from];
    head[from]=cnt;
}
bool dfs(int x, int c)
{
    if(color[x]) 
        return color[x]==c;
	color[x] = c;
	for (int i=head[x];i;i=e[i].nxt)
	{
	    int j=e[i].to;
        if(!dfs(j, e[i].w?c:(3-c)))
            return 0;
	}
	return 1;
}
void solve()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=m;i++)
    {
        int sz;cin>>sz;
        for(int j=1;j<=sz;j++)
        {
            int g;cin>>g;
            if(q[g].size()>0)
            {
                add(i,q[g][0],a[g]);
                add(q[g][0],i,a[g]);
            }
            else
                q[g].push_back(i);
        }
    }
    for(int i=1;i<=m;i++)
    {
        if(!color[i])
        {
            if(!dfs(i,1))
            {
                cout<<"NO"<<endl;return;
            }
        }
    }
    cout<<"YES"<<endl;
}
signed main()
{
    ios;
    solve();
    return 0;
}

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
64
65
66
67
68
69
70
71
72
73
74

最大完美匹配KM算法

https://www.bilibili.com/video/BV1cT411J7W5?spm_id_from=333.999.0.0&vd_source=91973ada1213cf6ba2cbb43a2bebd2e8
注释在代码中，详细则要需要观看大佬视频

#include
#define int long long
#define endl '\n'
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
using namespace std;
const int N=5e3+5;
const int inf=0x3f3f3f3f;
int match[N];       //右部点匹配了哪个左部点
int va[N],vb[N];    //标记是否在交替路中
int la[N],lb[N];    //左顶标、右顶标的值
int w[N][N],d[N];   //维护更新的delta值
int n;
bool dfs(int x)
{
    va[x]=1;
    for(int y=1;y<=n;y++)
    {
        if(!vb[y])
        {
            if(la[x]+lb[y]-w[x][y]==0)
            {
                vb[y]=1;
                if(!match[y]||dfs(match[y]))
                {
                    match[y]=x;return 1;
                }
            }
        }
        else //不是相等子图则记录i最小的d[y]
            d[y]=min(d[y],la[x]+lb[y]-w[x][y]);
    }
    return 0;
}
int KM()
{
    //预处理
    for(int i=1;i<=n;i++) la[i]=-inf;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        la[i]=max(la[i],w[i][j]);
    for(int i=1;i<=n;i++)
        lb[i]=0;
    for(int i=1;i<=n;i++)
    {
        while(1)
        {
            fill(va+1,va+n+1,0);
            fill(vb+1,vb+n+1,0);
            fill(d+1,d+n+1,inf);
            if(dfs(i)) break;
            int delta=inf;
            for(int j=1;j<=n;j++)
                if(!vb[j]) delta=min(delta,d[j]);
            for(int j=1;j<=n;j++)
            {
                if(va[j]) la[j]-=delta;
                if(vb[j]) lb[j]-=delta;
            }
        }
    }
}
void solve()
{
    memset(w,-inf,sizeof w);

}
signed main()
{
    ios;
    int t;cin>>t;
    while(t--)
    {
        solve();
    }
    return 0;
}

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77

P2457 [SDOI2006]仓库管理员的烦恼

思路：
1.模板求的是最大完美匹配，而本题需要使用二分图KM算法，却求的是最小代价。
2.需要变型。左部点为货物，右部点为仓库。将第i种货物搬到第j个仓库所需代价，注意要减去该仓库本身就有的该类货物。
3.最小代码，将权值取反，跑最大完全匹配。再将最后结果取反。

代码：

#include
#define int long long
#define endl '\n'
#define For(i,a,b) for(i=(a);i<=(b);++i)
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
using namespace std;
const int N=5e2+5;
const int inf=0x3f3f3f3f;
int match[N];       //右部点匹配了哪个左部点
int va[N],vb[N];    //标记是否在交替路中
int la[N],lb[N];    //左顶标、右顶标的值
int w[N][N],d[N];   //维护更新的delta值
int n,sum[N],mp[N][N];
bool dfs(int x)
{
    va[x]=1;
    for(int y=1;y<=n;y++)
    {
        if(!vb[y])
        {
            if(la[x]+lb[y]-w[x][y]==0)
            {
                vb[y]=1;
                if(!match[y]||dfs(match[y]))
                {
                    match[y]=x;return 1;
                }
            }
            else //不是相等子图则记录i最小的d[y]
                d[y]=min(d[y],la[x]+lb[y]-w[x][y]);
        }
    }
    return 0;
}
int KM()
{
    //预处理
    for(int i=1;i<=n;i++) la[i]=-inf;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        la[i]=max(la[i],w[i][j]);
    for(int i=1;i<=n;i++)
        lb[i]=0;
    for(int i=1;i<=n;i++)
    {
        while(1)
        {
            fill(va+1,va+n+1,0);
            fill(vb+1,vb+n+1,0);
            fill(d+1,d+n+1,inf);
            if(dfs(i)) break;
            int delta=inf;
            for(int j=1;j<=n;j++)
                if(!vb[j]) delta=min(delta,d[j]);
            for(int j=1;j<=n;j++)
            {
                if(va[j]) la[j]-=delta;
                if(vb[j]) lb[j]+=delta;
            }
        }
    }
    int res=0;
    for(int i=1;i<=n;i++)
        res+=w[match[i]][i];
    return res;
}

void solve()
{
    memset(w,-inf,sizeof w);
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
    {
        int x;cin>>x;
        mp[i][j]=x; //仓库---货物
        sum[j]+=x;  //每种货物总数
    }
    for(int i=1;i<=n;i++) //该种货物搬到第j个仓库所需代价
    {
        for(int j=1;j<=n;j++)
            w[i][j]=-(sum[i]-mp[j][i]);
    }
    cout<<-KM()<<endl;
}
signed main()
{
    //ios;
    solve();
    return 0;
}

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92

---

B. Party

这个B题属实有点卡我了，想不到思路，有点巧妙
思路：
1.若m为偶数，则所有成对出现的队员都可参与，怨气值为0.
2.若m为奇数，面临两种选择，一种是一对成员不可参加；一种是单个成员且出现次数为奇数队员不可参加。出现奇数次的队员不去，则m-奇数为偶数，符合题意。

#include
#define int long long
#define endl '\n'

using namespace std;
const int N=5e5+5;
const int inf=0x3f3f3f3f;
int n,m,a[N],d[N];

signed main()
{
    int t;cin>>t;
    while(t--)
    {
        cin>>n>>m;
        for(int i=1;i<=n;i++)
            cin>>a[i],d[i]=0;
        int s1=inf,s2=inf;
        for(int i=1;i<=m;i++)
        {
            int x,y;cin>>x>>y;
            d[x]++,d[y]++;
            s1=min(a[x]+a[y],s1);
        }
        if(m%2)
        {
            for(int i=1;i<=n;i++)
                if(d[i]&1)
                s2=min(s2,a[i]);
            cout<<min(s1,s2)<<endl;
        }
        else
            cout<<0<<endl;
    }
    return 0;
}

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

A. Perfect Permutation

记住这个排列，很有用: n 1 2 3 4 …… n-1

#include 
#define int long long
#define endl '\n'

using namespace std;
const int N =2e5+100;
const int mod=998244353;
const int inf=0x3f3f3f3f;
int n;

signed main()
{
    int t;cin>>t;
    while(t--)
    {
        cin>>n;
        if(n==1)
        {
            cout<<1<<endl;continue;
        }
        cout<<n<<" ";
        for(int i=1;i<n;i++)
            cout<<i<<" ";
        cout<<endl;
    }
    return 0;
}

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