上下界网络流

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
*/