上下界网络流

Posted on | In ,

cf704D

给棋盘上n个棋子染色，红黑两种，代价不同，有m个约束，要求某一行或某一列的红黑棋子数差不能超过某一数值。求最小代价的染色方案。

上下界网络流的思路就是分别减去最低流量，剩余的放在图中跑最大流，对于原有大于零下界的边就通过新建超级源点ss和汇点tt解决，即出点多出的连向汇点，入点缺少的从源点补充。合法要求：源点s发出的必须能跑满，否则原有的平衡条件就打破了，无可行流。

对于原本就有源的情况如下图，先确立一个可行流，取t-s边的流量，再把t-s边去掉，跑最大流加上即可。

20180406145614611

先明确建图方案。对某一行列的属性做文章的时候考虑裂点，我们用所有的xy坐标作点，原有的（x，y）点变成x->y边，表示由x选中它的同时会对y造成影响。这样形成了一个二分图，我们令某条边选便宜颜色的时候取流1，否则取0，这样原优化问题就变成了最大流问题，流量越大选取的便宜颜色越多。我们同时建立源点s汇点t，从s向每个x连边，容量表示每行能允许的某种颜色的数量（如果无限制则是该行上的点数，有限制则出现上下界），y同理连向t。这里我们发现出现了上下界网络流问题。套用上面算法解决即可。

在dinic的bfs中，如果把两个&&改成||会超时，按理说是完全等价的写法……这里卡了半天找原因。

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
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
#include<bits/stdc++.h>
using namespace std;

const int maxn=1e5+4;
#define ll long long
#define inf 0x3f3f3f3f
map<int,int> name[2];   //x,y的离散化映射
int cntx,cnty;  //用每个坐标值出现的顺序代表这个点

struct edge{
    int to,next;
    ll cap;     //cap是剩余可用流量
}es[maxn<<3];//最多可能有两倍的附加边，6*maxn
int st,ed,s,t,ss,tt;
int cnt=1,head[maxn<<1];
int cur[maxn<<1];
int forbid[maxn<<1];
inline void add(int u,int v,ll d){
    es[++cnt]=(edge){ v,head[u],d};
    head[u]=cnt;
}
inline void add1(int u,int v,ll d){
    add(u,v,d);
    add(v,u,0);
}
inline void add2(int u,int v,ll least,ll most){
    add1(u,v,most-least);
    add1(ss,v,least);
    add1(u,tt,least);
}

int tot[2][maxn],limit[2][maxn],p[maxn][2],num[maxn<<1];    //tot record the degree of a point,limit the min difference,num record the addr of origin edge of a point
int n,m,r,b;
int flag=1;
int total=0;    //点的总数
int level[maxn<<1]; //bfs中确认的层数
bool bfs(){
    memset(level,0,sizeof(level));
    queue<int> q;
    q.push(st);level[st]=1;	//这里必须写！！否则会无限回退到第一个点
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=head[u];i;i=es[i].next){
            int v=es[i].to;
            if(!level[v]&&es[i].cap>0&&forbid[v]==0){
                level[v]=level[u]+1;
                q.push(v);
            }
        }
    }
    return level[ed];
}

ll dfs(int x,ll f){
    if(x==ed||f==0)
        return f;
    ll res=0,tmp;
    for(int &i=cur[x];i;i=es[i].next){
        int v=es[i].to;
        if(level[v]==level[x]+1&&es[i].cap>0&&res<f){
            tmp=dfs(v,min(f-res,es[i].cap));
            es[i].cap-=tmp;es[i^1].cap+=tmp;
            res+=tmp;
        }
        if(res>=f)
            break;
    }
    if(!res)
        level[x]=0; //x点已经没用了
    return res;
}

int main(){
    cin>>n>>m>>r>>b;
    if(r>b){
        swap(r,b);flag=0;
    }
    for(int x,y,i=1;i<=n;i++){
        scanf("%d%d",&x,&y);
        if(!name[0][x])
            name[0][x]=++cntx;
        if(!name[1][y])
            name[1][y]=++cnty;
        p[i][0]=name[0][x];
        p[i][1]=name[1][y];
        tot[0][p[i][0]]++;
        tot[1][p[i][1]]++;
    }
    memset(limit,inf,sizeof(limit));
    for(int i=1,t,l,d;i<=m;i++){
        scanf("%d%d%d",&t,&l,&d);
        if(t==1){
            int x=name[0][l];
            limit[0][x]=min(limit[0][x],d);   //the smaller the d,the more restrictive it is
        }else{
            int y=name[1][l];
            limit[1][y]=min(limit[1][y],d);
        }
    }
    total=cntx+cnty;
    s=++total;t=++total;
    ss=++total;tt=++total;
    for(int x,y,i=1;i<=n;i++){  //添加边
        x=p[i][0],y=p[i][1];
        add1(x,y+cntx,1);
        num[i]=cnt;
    }
    for(int i=1;i<=cntx;i++){
        if(limit[0][i]==inf){
            add1(s,i,tot[0][i]);
        }else{
            ll least=(tot[0][i]-limit[0][i]+1)/2;
            ll most=(tot[0][i]+limit[0][i])/2;
            if(least>most) return puts("-1");   //这种情况说明总数奇数且要求两者差为0，要求无法满足
            add2(s,i,least,most);
        }
    }
    for(int i=1;i<=cnty;i++){
        if(limit[1][i]==inf){
            add1(i+cntx,t,tot[1][i]);
        }else{
            ll least=(tot[1][i]-limit[1][i]+1)/2;
            ll most=(tot[1][i]+limit[1][i])/2;
            if(least>most) return puts("-1");
            add2(i+cntx,t,least,most);
        }
    }
    add1(t,s,inf);
    st=ss,ed=tt;
    ll tmp=0;

    while(bfs()){
        for(int i=1;i<=total;++i) cur[i]=head[i];
        dfs(st,inf);
    }
    tmp=es[cnt].cap;    //选取t->s的流量（反向边的cap），不能直接取ss->tt的最大流，因为有的没经过t->s边
    ll judge=0;
    for(int i=head[ss];i;i=es[i].next){
        judge+=es[i].cap;
    }
    if(judge>0){    //if extra edges aren't used up, then invalid
        puts("-1");
        return 0;
    }
    st=s,ed=t;
    es[cnt].cap=es[cnt^1].cap=0;    //这一步是把s到t的连边正反都取消
    forbid[ss]=forbid[tt]=1;
    while(bfs()){
        for(int i=1;i<=total;++i) cur[i]=head[i];
        tmp+=dfs(st,inf);
    }
    ll ans=(ll)r*(tmp)+(ll)b*(n-tmp);
    cout<<ans<<endl;
    for(int i=1;i<=n;i++){
        int o=0;
        if(es[num[i]^1].cap==0){
            //如果出边用了,就说明这个点选小的
            o=1;
        }
        if(!flag)
            o^=1;
        putchar(o?'r':'b');
    }
    cout<<endl;
    return 0;
}

/*
4 1
1 2
1 1
1 2
2 1
2 2
1 1 1
*/