Not a real world problem 最小割+方案

(Updated: )
(8 mins to read)

有h*w的网格,每个点有权值h[i][j], 有n个粒子,告诉你每个点的坐标(x,y),权值的绝对值$\left| p[i]\right|$,定义价值为$\sum p[i]*h[x[i]][y[i]] + \sum p[i]*p[j]$(如果i点和j点相邻)问如何分配p的正负号可以最大化价值,并输出方案

做法

这种分配到两个集合,然后定义一下价值并最大化的可以考虑转化为最小割,s代表+号,t代表-号,那么对于每个粒子i:s->i,权值为p[i]*h[x[i]][y[i]](表示如果割掉,则p为负号,会损失这么多),同理i->t,权值为-p[i]*h[x[i]][y[i]],注意不能有负权,所以全加一个偏移量offset.再考虑相邻点,如果符号相同有一种收获x,符号不同有一种收获y.其实只要从i向j连边x-y,从j向i也连边x-y.可以默认两者符号相同收获x,那么如果割掉i与j间的边,说明两者分别属于s和t,损失x-y.建完图最大流,输出方案只要从源点走权值>0的边,所有经过的点就是属于s的(即符号为正)

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 mp make_pair
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define fi first
#define se second
#define debug(x) cerr << #x << " " << x << '\n'
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pli = pair<ll,int>;
const int INF = 0x3f3f3f3f, maxn = 1e3 + 5;
const ll LINF = 1e18 + 5;
constexpr int mod = 1e9 + 7;
int h, w, n, p[maxn], a[maxn][maxn], x[maxn], y[maxn], state[maxn];
const int N = 1e4 + 5, M = 2e5 + 5;
int cnt, head[N];
bool vis[N];
struct node
{
  int next, to, w;
}e[M<<1];
inline void add(int u,int v,int w)
{
  e[++cnt].next = head[u];
  e[cnt].to = v;
  e[cnt].w = w;
  head[u] = cnt;
}
struct Dinic
{
  int n, m, s, t;
  int dep[N], cur[N];
  void init(int n,int s,int t)
  {
    this->s = s, this->t = t, this->n = n;
    cnt = 1, m = 0;
    memset(head,0,(n+1)*sizeof(int));
    memset(vis,0,(n+1)*sizeof(bool));
  }
  void addedge(int u,int v,int cap)
  {
    add(u,v,cap);
    add(v,u,0);
    m += 2;
  }
  bool bfs()
  {
    memset(dep,0,(n+1)*sizeof(int));
    memcpy(cur,head,(n+1)*sizeof(int));
    queue <int> q;
    q.push(s); dep[s] = 1;
    while(!q.empty())
    {
      int u = q.front(); q.pop();
      for(int i=head[u];i;i=e[i].next)
      {
        int v = e[i].to;
        if(!dep[v]&&e[i].w>0)
        {
          dep[v] = dep[u] + 1;
          q.push(v);
        }
      }
    }
    return dep[t];
  }
  int dfs(int u,int flow)
  {
    if(u==t||!flow) return flow;
    int used = flow;
    for(int i=cur[u];i;i=e[i].next)
    {
      cur[u] = i;
      int v = e[i].to;
      if(dep[v]==dep[u]+1)
      {
        int low = dfs(v,min(flow,e[i].w));
        e[i].w -= low; e[i^1].w += low;
        flow -= low;
        if(!flow) break;
      }
    }
    return used - flow;
  }
  int go()
  {
    int maxflow = 0;
    while(bfs()) maxflow += dfs(s,INF);
    return maxflow;
  }
  void dfs(int u)
  {
    vis[u] = 1;
    for (int i = head[u]; i; i = e[i].next)
    {
      if (e[i].w>0)
      {
        if (vis[e[i].to]) continue;
        state[e[i].to] = 1;
        dfs(e[i].to);
      }
    }
  }
}MF;
void solve()
{
  scanf("%d%d%d", &h, &w, &n);
  for(int i=1; i<=h; i++)
    for(int j=1; j<=w; j++)
      scanf("%d", &a[i][j]);
  for(int i=1; i<=n; i++)
    scanf("%d%d%d", x+i, y+i, p+i);
  MF.init(n+2, 0, n+1);
  int ans = n*100000;
  for(int i=1; i<=n; i++)
  {
    state[i] = 0;
    MF.addedge(MF.s, i, p[i]*a[x[i]][y[i]]+100000);
    MF.addedge(i, MF.t, -p[i]*a[x[i]][y[i]]+100000);
    for(int j=i+1; j<=n; j++)
      if(abs(x[i]-x[j])+abs(y[i]-y[j])<=1)
        MF.addedge(i, j, 2*p[i]*p[j]), MF.addedge(j, i, 2*p[i]*p[j]), ans += p[i]*p[j];
  }
  ans -= MF.go();
  printf("%d\n", ans);
  MF.dfs(MF.s);
  for(int i=1; i<=n; i++)
    if(state[i]) printf("1%c", " \n"[i==n]);
    else printf("-1%c", " \n"[i==n]);
}
int main()
{
  int T; scanf("%d", &T);
  while(T--) solve();
  return 0;
}