Starry

发表于 更新于 分类于 本文字数： 539 阅读时长 ≈ 2 分钟

题意是维护一个带删除操作的可持久化并查集，但不会实现，于是看题解考虑离线操作，解决完一个儿子就回溯操作

注意到离线仍需要带删除操作的并查集，所以需要虚根来实现

一开始操作数组开大了N*30爆MLE，后来因为答案要求的是Yes和No，而打的是YES和NO给了几发WA

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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
const int N = 1e6 + 86;
int fa[N * 2], flag[N], sz[N * 2], tot, n, m, ans[N], dp[N * 2];
vi v[N];
struct NODE
{
    int op, a, b;
} e[N];

int find(int x)
{
    if (x == fa[x])
        return x;
    else
        return find(fa[x]);
}

void dfs(int i)
{
    for (auto it : v[i])
    {
        int op = e[it].op;
        if (op == 4)
        {
            int a = e[it].a, b = e[it].b;
            if (flag[a] == -1 || flag[b] == -1)
            {
                ans[it] = 0;
                dfs(it);
                continue;
            }
            int oa = find(flag[a]), ob = find(flag[b]);
            if (oa == ob)
                ans[it] = 1;
            else
                ans[it] = 0;
            dfs(it);
        }
        if (op == 5)
        {
            if (flag[e[it].a] == -1)
            {
                ans[it] = 0;
                dfs(it);
                continue;
            }
            int oa = find(flag[e[it].a]);
            ans[it] = sz[oa];
            dfs(it);
        }
        if (op == 1)
        {
            int a = e[it].a, b = e[it].b;
            if (flag[a] == -1 || flag[b] == -1)
            {
                dfs(it);
                continue;
            }
            int oa = find(flag[a]), ob = find(flag[b]), cap = 0;
            if(oa==ob){
                dfs(it);
                continue;
            }
            if(dp[oa] == dp[ob]){
                fa[ob] = oa; sz[oa] += sz[ob]; dp[oa]++;
                dfs(it);
                fa[ob] = ob; sz[oa] -= sz[ob]; dp[oa]--;
            }else{
                if(dp[oa] < dp[ob]) swap(oa, ob);
                fa[ob] = oa; sz[oa] += sz[ob];
                dfs(it);
                fa[ob] = ob; sz[oa] -= sz[ob];
            }
        }
        if (op == 2)
        {
            int a = e[it].a;
            if (flag[a]==-1){
                dfs(it);
                continue;
            }
            int oa=find(flag[a]),aa=flag[a];
            flag[a]=-1;
            sz[oa]--;
            dfs(it);
            sz[oa]++;
            flag[a]=aa;
        }
        if(op==3){
            int a = e[it].a, b = e[it].b;
            if (flag[a] == -1 || flag[b] == -1)
            {
                dfs(it);
                continue;
            }
            int oa = find(flag[a]), ob = find(flag[b]),aa=flag[a];
            if(oa==ob){
                dfs(it);
                continue;
            }
            sz[oa]--;
            sz[ob]++;
            flag[a]=++tot;
            sz[flag[a]]=1;
            fa[flag[a]]=ob;
            dfs(it);
            sz[oa]++;
            sz[ob]--;
            flag[a]=aa;
        }
    }
}

int main()
{
    //IN;OUT;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    tot = n + 1;
    int op, k, a, b=0;
    f(i, 1, n) flag[i] = fa[i] = i, sz[i] = 1;
    f(i, 1, m)
    {
        cin >> op >> k >> a;
        if (op != 2 && op != 5)
            cin >> b;
        v[k].pb(i);
        e[i] = (NODE){op, a, b};
    }
    dfs(0);
    f(i,1,m){
        if(e[i].op==4){
            if(ans[i])cout<<"Yes\n";
            else cout<<"No\n";
        }
        else if(e[i].op==5)cout<<ans[i]<<"\n";
    }
    return 0;
}

发表于 更新于 分类于 本文字数： 428 阅读时长 ≈ 2 分钟

题意为给定一个二分图，左右点数均为n，并给定左右相连的边，对这些边两端点满足,并且原图左边点的度数

现给定你一些限制条件并要求你选定一些点及其边，使得右边的点全部被覆盖到

状态压缩dp：

设以数组dp[i][j]其中表示二进制下中前位反应左边点的选取情况，后至位表示右边点的覆盖情况，注意判断是否满足的情况，便可不用三维数组来dp

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
vi v[20], m(30);
LL dp[20][(1 << 20) - 1], tt, n, b[20];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> tt;
    f(sb, 1, tt)
    {
        string s;
        f(i, 1, 20)
        {
            v[i].clear();
            b[i] = 0;
        }
        cin >> n;
        f(i, 1, n)
        {
            cin >> s;
            f(j, 1, n)
            {
                if (s[j - 1] == '1')
                    v[i].pb(j);
            }
        }
        f(i, 1, n)
        {
            cin >> s;
            f(j, 1, n)
            {
                if (s[j - 1] == '1')
                    b[i] |= (1 << (n-j));
            }
        }
        f(i, 1, n) cin >> m[i];
        f(i, 1, n+1)
        {
            for (int j = 0; j < (1 << n); j++)
            {
                dp[i][j] = 2e8;
            }
        }
        dp[1][0] = 0;
        for (int i = 1; i <= n; i++)
        {
            for (int j = 0; j < (1 << n); j++)
            {
                if (dp[i][j] == 2e8)
                    continue;
                LL rs=(j&((1<<(n-i+1))-1)),ls=j&(((1<<n)-1)-((1<<(n-i+1))-1));
                if ((rs >> (n - i)) & 1)
                    dp[i + 1][j ^ (1 << (n - i))] = min(dp[i][j], dp[i + 1][j ^ (1 << (n - i))]);
                if (ls & b[i])
                {
                    continue;
                }
                for (LL ds = 1; ds < (1 << (v[i].size())); ds++)
                {
                    LL cost = 1, es = rs;
                    for (int k = 0; k < v[i].size(); k++)
                    {
                        if ((ds >> k) & 1)
                            cost *= m[i], es |= (1 <<(n- v[i][k]));
                    }
                    if (!((es >> (n - i)) & 1))
                        continue;
                    dp[i + 1][ls | es] = min(dp[i + 1][ls | es], dp[i][j] + cost);
                }
            }
        }
        LL ans = 2e8;
        for (int i = 0; i < (1 << n); i++)
        {
            ans = min(ans, dp[n+1][i]);
        }
        cout << (ans == 2e8 ? -1 : ans) << "\n";
    }
    return 0;
}

发表于 更新于 分类于 本文字数： 401 阅读时长 ≈ 1 分钟

考虑到问题

能使最多顾客满意呢

所以我们应以客人为主要限制目标，所以将其放中间，两边各连房间和菜，于是便可转化为最大流问题

建图应注意到客人只要一个，所以对每个客人应建两点，相连的权值为1，左边点与房间相连，右边点与菜相连

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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
const int N = 2e5 + 86;

struct egdes
{
    int to, nxt, w;
} e[N * 2];
int hd[N * 2], cur[N * 2], tot = 1, st, en;
vi lv;
void add(int x, int y, int w)
{
    e[++tot] = (egdes){y, hd[x], w};
    hd[x] = tot;
}

int bfs()
{
    lv.assign(N, 0);
    memcpy(cur, hd, sizeof(hd));
    queue<int> q;
    q.push(st);
    lv[st] = 1;
    while (!q.empty())
    {
        int p = q.front();
        q.pop();
        for (int eg = hd[p]; eg; eg = e[eg].nxt)
        {
            int to = e[eg].to, vol = e[eg].w;
            if (vol && !lv[to])
            {
                lv[to] = lv[p] + 1;
                q.push(to);
            }
        }
    }
    return lv[en];
}

int dfs(int ss, int flow)
{
    if (ss == en)
        return flow;
    int r = flow;
    for (int eg = cur[ss]; eg && r; eg = e[eg].nxt)
    {
        cur[ss] = eg;
        int to = e[eg].to, vol = e[eg].w;
        if (vol && lv[to] == lv[ss] + 1)
        {
            int c = dfs(to, min(r, vol));
            r -= c;
            e[eg].w -= c;
            e[eg ^ 1].w += c;
        }
    }
    return flow - r;
}
int rs, fj, cai;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> rs>>fj>>cai;
    st=rs+fj+cai+4,en=st+1;
    f(i,1,cai){
        add(st,i,1);
        add(i,st,0);
    }
    f(i,1,fj){
        add(rs+cai+i,en,1);
        add(en,rs+cai+i,0);
    }
    f(i,1,rs){
        add(cai+i,en+i,1);
        add(en+i,cai+i,0);
    }
    f(i, 1, rs)
    {
        f(j, 1, fj)
        {
            int x;
            cin >> x;
            if (x)
            {
                add(en+i,cai+rs+j,1);
                add(cai+rs+j,en+i,0);
            }
        }
    }
    f(i, 1,rs)
    {
        f(j, 1, cai)
        {
            int x;
            cin >> x;
            if (x)
            {
                add(j,cai+i,1);
                add(cai+i,j,0);
            }
        }
    }
    LL ans=0;
    while(bfs()){
        ans+=dfs(st,3e8);
    }
    cout<<ans;
    return 0;
}

发表于 更新于 分类于 本文字数： 345 阅读时长 ≈ 1 分钟

对于同意午睡的，源点到该点权值为1，该点到源点权值为0.

而对于好朋友，则两点建立双向边，权值均为1

对于多对好朋友冲突，我们贪心地取最少的那一边使得总冲突数最少，对于此即为最小割最大流。

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
const int N=5e5+86;

struct egdes{
    int to,nxt,w;
}e[N*2];int hd[N*2],cur[N*2],tot=1,st,en;
vi lv;
void add(int x,int y,int w){
    e[++tot]=(egdes){y,hd[x],w};
    hd[x]=tot;
}

int bfs(){
    lv.assign(N,0);
    memcpy(cur,hd,sizeof(hd));
    queue<int> q;
    q.push(st);
    lv[st]=1;
    while(!q.empty()){
        int p=q.front();
        q.pop();
        for(int eg=hd[p];eg;eg=e[eg].nxt){
            int to=e[eg].to,vol=e[eg].w;
            if(vol&&!lv[to]){
                lv[to]=lv[p]+1;
                q.push(to);
            }
        }
    }
    return lv[en];
}

int dfs(int ss,int flow){
    if(ss==en)
    return flow;
    int r=flow;
    for(int eg=cur[ss];eg&&r;eg=e[eg].nxt){
        cur[ss]=eg;
        int to=e[eg].to,vol=e[eg].w;
        if(vol&&lv[to]==lv[ss]+1){
            int c=dfs(to,min(r,vol));
            r-=c;
            e[eg].w-=c;
            e[eg^1].w+=c;
        }
    }
    return flow-r;
}
int nn,mm;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>nn>>mm;
    st=nn+11,en=st+1;
    f(i,1,nn){
        int x;
        cin>>x;
        if(x){
            add(st,i,1);
            add(i,st,0);
            add(i,en,0);
            add(en,i,0);
        }
        else {
            add(st,i,0);
            add(i,st,0);
            add(i,en,1);
            add(en,i,0);
        }
    }
    f(i,1,mm){
        int x,y;
        cin>>x>>y;
        add(x,y,1);
        add(y,x,1);
    }
    LL ans=0;
    while(bfs()){
        ans+=dfs(st,3e8);
    }
    cout<<ans;
    return 0;
}

发表于 更新于 分类于 本文字数： 273 阅读时长 ≈ 1 分钟

最大流问题，建图时注意每排座位有两人

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
const int N=2e4+86;
struct egdes{
    int to,nxt,w;
}e[N*2];int hd[N*2],cur[N*2],tot=1,st,en;
vi lv;
void add(int x,int y,int w){
    e[++tot]=(egdes){y,hd[x],w};
    hd[x]=tot;
}

int bfs(){
    lv.assign(N,0);
    memcpy(cur,hd,sizeof(hd));
    queue<int> q;
    q.push(st);
    lv[st]=1;
    while(!q.empty()){
        int p=q.front();
        q.pop();
        for(int eg=hd[p];eg;eg=e[eg].nxt){
            int to=e[eg].to,vol=e[eg].w;
            if(vol&&!lv[to]){
                lv[to]=lv[p]+1;
                q.push(to);
            }
        }
    }
    return lv[en];
}

int dfs(int ss,int flow){
    if(ss==en)
    return flow;
    int r=flow;
    for(int eg=cur[ss];eg&&r;eg=e[eg].nxt){
        cur[ss]=eg;
        int to=e[eg].to,vol=e[eg].w;
        if(vol&&lv[to]==lv[ss]+1){
            int c=dfs(to,min(r,vol));
            r-=c;
            e[eg].w-=c;
            e[eg^1].w+=c;
        }
    }
    return flow-r;
}
int m;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>m;
    st=2*m+1,en=2*m+2;
    f(i,1,2*m){
        add(st,i,1);
        add(i,st,0);
    }
    f(i,1,m){
        add(en+i,en,2);
        add(en,en+i,0);
    }
    f(i,1,2*m){
        int x,y;
        cin>>x>>y;
        add(i,x+en,1);
        add(x+en,i,0);
        add(i,y+en,1);
        add(y+en,i,0);
    }
    LL ans=0;
    while(bfs()){
        ans+=dfs(st,3e8);
    }
    cout<<ans;
    return 0;
}
0%