无知 无求

0%

hdu3338 Kakuro Extension

发表于 分类于 ，

一道很有意思的题目 如果不是出在网络流的套题里面我很可能就往精确覆盖问题去想然后用dlx来搞了..?

题目意思是给你一个n*m的方格图 白格里填1-9的数字是横向和纵向之和都满足给的约束条件 既然在网络流套题里就按照网络流的思路来想呗
一开始想的还有些问题 第一次跑出来全是9吓得我仔细寻找了一下是不是模板又改错了…

正确的建图思路大概是 每个纵列或横行的约束看作一个点 每个白格看作一个点 源点连横行约束 容量是给定容量（这里为了好理解暂定这样 后面为了适应条件会做小小的改动）
纵列约束连汇点 容量也是给定容量 横约束连它控制的白格 容量是9 白格再连它所属的纵约束 容量一样 这样跑一遍最大流 观察经过每个白格的流量就是应该填的数字（注意是流量而不是剩余流量）

这样还会遇到一个问题 就是会有流量为0的边出现 仔细看条件的话会发现白格是不允许填0的 所以我们需要限制一下边的下界 但是仔细思考一下 通过一些小的改变 我们实际避免这个问题 每个白格一定至少需要流过1的流量（原题未提无解情况 理解为默认有解） 那么我们可以预先保证每个白格流过1但是不在图中计算 这样原来容量为9的变成容量为8，约束的容量减掉它控制的白格数量 在最后计算流量的时候再加上1即可

在这里为了方便检查流量 我将白格拆点并编号 保证与编号一致的边正好是我们需要检查的边 来方便检查流量以确定结果

AC代码

++
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
#include <cstdio>
#include <vector>
#include <cstring>
#include<algorithm>
#include <queue>
using namespace std;
const int MAXV = 20050;
const int maxm=100050;
const int INF = 1<<30;
int edge;
int level[MAXV];
int iter[MAXV]; //当前弧，之前的已经没有用了
int head[MAXV];
struct edgenode
{
    int from;
    int to;//边的指向
    int cap;//边的容量
    int next;//链表的下一条边
} edges[maxm];
void init()
{
    edge=0;
    memset(head,-1,sizeof(head));
}
void addedge(int from, int to, int cap) {
    edges[edge].from=from;
    edges[edge].cap=cap;
    edges[edge].to=to;
    edges[edge].next=head[from];
    head[from]=edge++;
    edges[edge].from=to;
    edges[edge].cap=0;
    edges[edge].to=from;
    edges[edge].next=head[to];
    head[to]=edge++;
}

void bfs(int s) {
    memset(level, -1, sizeof level);
    std::queue<int> que;
    level[s] = 0;
    que.push(s);
    while (!que.empty()) {
        int v = que.front(); que.pop();
        for (int i = head[v]; i !=-1; i=edges[i].next) {
            edgenode &e = edges[i];
            if (e.cap > 0 && level[e.to] < 0) {
                level[e.to] = level[v] + 1;
                que.push(e.to);
            }
        }
    }
}

int dfs(int v, int t, int f) {
    if (v == t) return f;
    if(iter[v]==0)
    {
        iter[v]=head[v];
    }
    for (int &i = iter[v]; i !=-1; i=edges[i].next) { // 注意i是引用 实现当前弧优化
        edgenode &e = edges[i];
        if (e.cap > 0 && level[v] < level[e.to]) {
            int d = dfs(e.to, t, std::min(f, e.cap));
            if (d > 0) {
                e.cap -= d;
                edges[i^1].cap += d;
                return d;
            }
        }
    }
    return 0;
}

int maxflow(int s, int t) {
    int flow = 0;
    for (; ;) {
        bfs(s);
        if (level[t] < 0) return flow;
        memset(iter, 0, sizeof iter);
        int f;
        while ((f = dfs(s, t, INF)) > 0) {
            flow += f;
        }
    }
    return flow;
}
int row[120][120],col[120][120],name[120][120],pos;
int todigit(char *dig)
{
    return (dig[0]-'0')*100+(dig[1]-'0')*10+(dig[2]-'0');
}
int main()
{
    int n,m;
    while(~scanf("%d%d",&n,&m))
    {
        memset(row,-1,sizeof(row));
        memset(col,-1,sizeof(col));
        memset(name,-1,sizeof(name));
        init();
        pos=0;
        char item[10];
        for(int i=0;i<n;++i)
        {
            for(int j=0;j<m;++j)
            {
                scanf("%s",item);
                if(item[0]=='.')
                {
                    name[i][j]=pos;
                    addedge(pos*2,pos*2+1,8);
                    pos++;
                }
                else
                {
                    if(item[0]!='X')
                    {
                        col[i][j]=todigit(&item[0]);
                    }
                    if(item[4]!='X')
                    {
                        row[i][j]=todigit(&item[4]);
                    }
                }
            }
        }
        int start=pos*2,end=pos*2+1,cons=pos*2+2;
        for(int i=0;i<n;++i)
        {
            for(int j=0;j<m;++j)
            {
                if(row[i][j]!=-1)
                {
                    int cotmp=j+1,num=0;
                    while(cotmp<m&&name[i][cotmp]!=-1)
                    {
                        addedge(cons,name[i][cotmp]*2,INF);
                        ++cotmp,++num;
                    }
                    addedge(start,cons,row[i][j]-num);
                    ++cons;
                }
                if(col[i][j]!=-1)
                {
                    int rotmp=i+1,num=0;
                    while(rotmp<n&&name[rotmp][j]!=-1)
                    {
                        addedge(name[rotmp][j]*2+1,cons,INF);
                        ++rotmp,++num;
                    }
                    addedge(cons,end,col[i][j]-num);
                    ++cons;
                }
            }
        }
        int ans=maxflow(start,end);
        for(int i=0;i<n;++i)
        {
            for(int j=0;j<m;++j)
            {
                if(name[i][j]==-1)
                {
                    printf("_ ");
                }
                else
                {
                    printf("%d ",9-edges[name[i][j]*2].cap);
                }
            }
            printf("\n");
        }
    }
    return 0;
}