Eternity

Until The End

P1231 教辅的组成 & P1402 酒店之王 & P2891 [USACO07OPEN]Dining G

发表于 分类于
本文字数： 9.2k 阅读时长 ≈ 8 分钟

网络流建模经典题的三倍经验。

如果知道是网络流的话，可以很快把图建出来。

考虑三分图匹配。

用基辅的组成来说这道题。

对照课本，练习册，答案分别建图，一共 $\mathcal O(N_1+N_2+N_3)$ 的点，然后让课本作为贡献体（三分图的中间部分），左连答案，右连练习册，答案连源点，练习册连汇点。

然后开心地过了样例，交一发，$10pt$ 。

为什么呢？

我们考虑下面一组数据：

练习册一能和课本一配对，答案一能和课本一配对，很明显这三点可以做一套；
练习册二能和课本一配对，答案二能和课本一配对，很明显这三点可以做一套。

但在题目里，这只能有一套，是很明显的。

但是，我们把这一套数据带进我们的网络里，会发现跑出来的答案依然是 $2$ 。

网络的容量来源于边权，结点不过是一个转载体，不存储，不产生，不滞留任何流，所以，在我们建的网络中，实际上只有两层贡献限制，而在题目中，我们有三层贡献限制。

想到树链剖分里有一个操作叫边权挂点，即用点来维护边的权值。那么，在网络流里面，我们是不是也可以考虑一个点权挂边的操作呢。

很明显，这是行得通的。

有一种思路，学术上的名字叫拆点。

顾名思义，把一个点拆成两个点，并在其中连上通过这个点的代价。

通过这个思路来解决我们建图的缺漏，我们并没有计算使用课本的代价，所以，我们把原来的第 $i$ 个点拆成 $i_{in},i_{out}$ 。并连接一条从 $i_{in}$ 到 $i_{out}$ 容量为 $1$ 的边，表示第 $i$ 个贡献体最多只能贡献 $1$ 即可。

然后捏，另外两道题同理，用一样的方法处理即可。

空间复杂度 $\mathcal O(4n+2(n+m))$ 。

AC Code P1231 
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
140
141
142
143
144
145
146
#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=getchar(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline void write(T x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
template<>
inline void write(char c)
{
    putchar(c);
}
template<>
inline void write(char *s)
{
    while(*s) putchar(*s++);
}
template<class T,class ...T1>
inline void write(T x,T1 ...x1)
{
    write(x),write(x1...);
}
template<class T>
inline bool checkMax(T &x,T y)
{
    return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T y)
{
    return x>y?x=y,1:0;
}
const int MAXN=4e4+10,MAXM=2e5+10;
const int INF=0x3f3f3f3f;
int N,M,S,T;
struct Net
{
    int next,to,val;
}Edge[MAXM<<1];
int Head[MAXN],Cur[MAXN],Total=1;
inline void addEdge(int u,int v,int w)
{
    Edge[++Total]=(Net){Head[u],v,w};Head[u]=Total;
    Edge[++Total]=(Net){Head[v],u,0};Head[v]=Total;
}
int A,B,C;
int Fl[MAXN];
inline bool Bfs()
{
    memset(Fl,-1,sizeof(Fl));
    std::queue<int>Q;
    Q.push(S),Cur[S]=Head[S],Fl[S]=0;
    while(!Q.empty())
    {
        int u=Q.front();Q.pop();
        for(int e=Head[u],v;e;e=Edge[e].next)
        {
            v=Edge[e].to;
            if(Fl[v]==-1&&Edge[e].val)
            {
                Fl[v]=Fl[u]+1;
                Cur[v]=Head[v];
                if(v==T) return 1;
                Q.push(v);
            }
        }
    }
    return 0;
}
int Dfs(int x,int inf)
{
    if(x==T) return inf;
    int flow=0;
    for(int e=Cur[x],v;e&&flow<inf;e=Edge[e].next)
    {
        Cur[x]=e,v=Edge[e].to;
        if(Fl[v]==Fl[x]+1&&Edge[e].val)
        {
            int k=Dfs(v,std::min(Edge[e].val,inf-flow));
            if(!k) Fl[v]=-1;
            Edge[e].val-=k,Edge[e^1].val+=k,flow+=k;
        }
    }
    return flow;
}
inline int Dinic()
{
    int r=0,flow;
    while(Bfs()) while(flow=Dfs(S,INF)) r+=flow;
    return r;
}
int main()
{
    // freopen("netflow.in","r",stdin);
    // freopen("netflow.out","w",stdout);
    read(A,B,C);
    read(M);S=0,T=A+A+B+C+1;
    for(int i=1,u,v;i<=M;++i)
    {
        read(u,v);
        addEdge(u+A+C,v+A+A+C,1);
    }
    read(M);
    for(int i=1,u,v;i<=M;++i)
    {
        read(u,v);
        addEdge(v,u+C,1);
    }
    for(int i=1;i<=A;++i) addEdge(i+C,i+A+C,1);
    for(int i=1;i<=B;++i) addEdge(i+A+A+C,T,1);
    for(int i=1;i<=C;++i) addEdge(S,i,1);
    write(Dinic());
    return 0;
}
/*
5 3 4
5
4 3
2 2
5 2
5 1
5 3
5
1 3
3 1
2 2
3 3
4 3
*/
AC Code P1402 
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
#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=getchar(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline void write(T x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
template<>
inline void write(char c)
{
    putchar(c);
}
template<>
inline void write(char *s)
{
    while(*s) putchar(*s++);
}
template<class T,class ...T1>
inline void write(T x,T1 ...x1)
{
    write(x),write(x1...);
}
template<class T>
inline bool checkMax(T &x,T y)
{
    return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T y)
{
    return x>y?x=y,1:0;
}
const int MAXN=4e2+10,MAXM=2e5+10;
const int INF=0x3f3f3f3f;
int N,P,Q,S,T;
struct Net
{
    int next,to,val;
}Edge[MAXM<<1];
int Head[MAXN],Cur[MAXN],Total=1;
inline void addEdge(int u,int v,int w)
{
    Edge[++Total]=(Net){Head[u],v,w};Head[u]=Total;
    Edge[++Total]=(Net){Head[v],u,0};Head[v]=Total;
}
int Fl[MAXN];
inline bool Bfs()
{
    memset(Fl,-1,sizeof(Fl));
    std::queue<int>Q;
    Q.push(S),Cur[S]=Head[S],Fl[S]=0;
    while(!Q.empty())
    {
        int u=Q.front();Q.pop();
        for(int e=Head[u],v;e;e=Edge[e].next)
        {
            v=Edge[e].to;
            if(Fl[v]==-1&&Edge[e].val)
            {
                Fl[v]=Fl[u]+1;
                Cur[v]=Head[v];
                if(v==T) return 1;
                Q.push(v);
            }
        }
    }
    return 0;
}
int Dfs(int x,int inf)
{
    if(x==T) return inf;
    int flow=0;
    for(int e=Cur[x],v;e&&flow<inf;e=Edge[e].next)
    {
        Cur[x]=e,v=Edge[e].to;
        if(Fl[v]==Fl[x]+1&&Edge[e].val)
        {
            int k=Dfs(v,std::min(Edge[e].val,inf-flow));
            if(!k) Fl[v]=-1;
            Edge[e].val-=k,Edge[e^1].val+=k,flow+=k;
        }
    }
    return flow;
}
inline int Dinic()
{
    int r=0,flow;
    while(Bfs()) while(flow=Dfs(S,INF)) r+=flow;
    return r;
}
int main()
{
    // freopen("netflow.in","r",stdin);
    // freopen("netflow.out","w",stdout);
    read(N,P,Q);
    S=0,T=P+Q+N+N+1;
    for(int i=1;i<=N;++i)
        for(int j=1,x;j<=P;++j)
        {
            read(x);
            if(x) addEdge(i+Q+N,j+Q+N+N,1);
        }
    for(int i=1;i<=N;++i)
        for(int j=1,x;j<=Q;++j)
        {
            read(x);
            if(x) addEdge(j,i+Q,x);
        }
    for(int i=1;i<=N;++i) addEdge(i+Q,i+Q+N,1);
    for(int i=1;i<=P;++i) addEdge(i+Q+N+N,T,1);
    for(int i=1;i<=Q;++i) addEdge(S,i,1);
    write(Dinic());
    return 0;
}
/*
2 2 2
1 0
1 0
1 1
1 1
*/
AC Code P2891 
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
#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=getchar(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline void write(T x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
template<>
inline void write(char c)
{
    putchar(c);
}
template<>
inline void write(char *s)
{
    while(*s) putchar(*s++);
}
template<class T,class ...T1>
inline void write(T x,T1 ...x1)
{
    write(x),write(x1...);
}
template<class T>
inline bool checkMax(T &x,T y)
{
    return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T y)
{
    return x>y?x=y,1:0;
}
const int MAXN=4e2+10,MAXM=2e5+10;
const int INF=0x3f3f3f3f;
int N,F,D,S,T;
struct Net
{
    int next,to,val;
}Edge[MAXM<<1];
int Head[MAXN],Cur[MAXN],Total=1;
inline void addEdge(int u,int v,int w)
{
    Edge[++Total]=(Net){Head[u],v,w};Head[u]=Total;
    Edge[++Total]=(Net){Head[v],u,0};Head[v]=Total;
}
int Fl[MAXN];
inline bool Bfs()
{
    memset(Fl,-1,sizeof(Fl));
    std::queue<int>Q;
    Q.push(S),Cur[S]=Head[S],Fl[S]=0;
    while(!Q.empty())
    {
        int u=Q.front();Q.pop();
        for(int e=Head[u],v;e;e=Edge[e].next)
        {
            v=Edge[e].to;
            if(Fl[v]==-1&&Edge[e].val)
            {
                Fl[v]=Fl[u]+1;
                Cur[v]=Head[v];
                if(v==T) return 1;
                Q.push(v);
            }
        }
    }
    return 0;
}
int Dfs(int x,int inf)
{
    if(x==T) return inf;
    int flow=0;
    for(int e=Cur[x],v;e&&flow<inf;e=Edge[e].next)
    {
        Cur[x]=e,v=Edge[e].to;
        if(Fl[v]==Fl[x]+1&&Edge[e].val)
        {
            int k=Dfs(v,std::min(Edge[e].val,inf-flow));
            if(!k) Fl[v]=-1;
            Edge[e].val-=k,Edge[e^1].val+=k,flow+=k;
        }
    }
    return flow;
}
inline int Dinic()
{
    int r=0,flow;
    while(Bfs()) while(flow=Dfs(S,INF)) r+=flow;
    return r;
}
int main()
{
    // freopen("netflow.in","r",stdin);
    // freopen("netflow.out","w",stdout);
    read(N,F,D);
    S=0,T=D+F+N+N+1;
    for(int i=1,nf,nd;i<=N;++i)
    {
        read(nf,nd);
        for(int j=1,x;j<=nf;++j) read(x),addEdge(i+D+N,x+D+N+N,1);
        for(int j=1,x;j<=nd;++j) read(x),addEdge(x,i+D,1);
        addEdge(i+D,i+D+N,1);
    }
    for(int i=1;i<=D;++i) addEdge(S,i,1);
    for(int i=1;i<=F;++i) addEdge(i+D+N+N,T,1);
    write(Dinic());
    return 0;
}
/*
4 3 3
2 2 1 2 3 1
2 2 2 3 1 2
2 2 1 3 1 2
2 1 1 3 3
*/
相关文章