题意：

黑格子右上代表该行的和，左下代表该列下的和

链接：点我

这题可以用网络流做。以空白格为节点，假设流是从左流入，从上流出的，流入的容量为行和，流出来容量为列和，其余容量不变。求满足的最大流。由于流量有上下限限制，可以给每个数都减掉1，则填出来的数字范围为0—8, 就可以用单纯的网络流搞定了。求出来再加上就可以了。

这一题主要是在建图

建图：

一共有四类点：

1. 构造源点ST，汇点ED

2. 有行和的格子，即\上面有值的格子，此类节点设为A

3. 空白格，设为B

4. 有列和的格子，即\下面有值的格子，设为C

则可以建边：

1. ST------------A         容量：行和

2. A----------- B          容量：8

3. B------------C          容量:8

4. C------------ED          容量:列和

当然，反向边容量都置为0。

就是这么难~~

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 using namespace std;

 #define INF 999999999

 #define MAXN 14000

 #define RE(x) (x)^1

 int head[MAXN];

 int map[][];

 int st,ed;

 struct Edge

 {

     int v,next;

     int val;

     Edge(){}

     Edge( int V , int NEXT , int W =  ):v(V),next(NEXT),val(W){}

 }edge[];

 struct gg

 {

     int x,y;

     int val;

 }row[MAXN],col[MAXN];

 int emp,row_num,col_num;

 int lvl[MAXN], gap[MAXN];

 int cnt_edge;

 int n,m,T;

 int empty[MAXN];

 void Insert_Edge( int u , int v , int flow =  ) {

     edge[cnt_edge] = Edge(v,head[u],flow);

     head[u] = cnt_edge++;

     edge[cnt_edge] = Edge(u,head[v]);

     head[v] = cnt_edge++;

 }

 void Init(){

     cnt_edge = ;

     memset(head,-,sizeof(head));

      memset(lvl, , sizeof (lvl));

     memset(gap, , sizeof (gap));

 }

 int dfs(int u, int flow)

 {

     if (u==ed) {

         return flow;

     }

     int tf = , sf, mlvl = ed-;

     for (int i= head[u]; i != -; i = edge[i].next) {

         if (edge[i].val > ) {

             if (lvl[u] ==lvl[edge[i].v]+) {

                 sf = dfs(edge[i].v, min(flow-tf, edge[i].val));

                 edge[i].val -= sf;

                 edge[RE(i)].val += sf;

                 tf += sf;

                 if (lvl[st] >=ed) {

                     return tf;

                 }

                 if (tf == flow) {

                     break;

                 }

             }

             mlvl = min(mlvl, lvl[edge[i].v]);

         }

     }

     if (tf == ) {

         --gap[lvl[u]];

         if (!gap[lvl[u]]) {

             lvl[st] =ed;

         }

         else {

             lvl[u] = mlvl+;

             ++gap[lvl[u]];

         }

     }

     return tf;

 }

 int sap()

 {

     int ans = ;

     gap[]=ed;

     while (lvl[st] <ed) {

         ans += dfs(st, INF);

     }

     return ans;

 }

 int print( int tp ) {

     int ans = ;

     int id = tp + row_num+;

     for( int i = head[id] ; i != - ; i = edge[i].next ) {

         int v = edge[i].v;

         if( v <=row_num+ )

         {

           ans+= edge[i].val;

           break;

         }

     }

     return ans+;

 }

 int main()

 {

     int i,j;

     char s[];

     while(scanf("%d%d",&n,&m)!=-)

     {

         emp=row_num=col_num=;

         for(i=;i<n;i++)

         for(j=;j<m;j++)

         {

             scanf("%s",s);

             if(s[]=='.')

             {

                 map[i][j]=++emp;

             }

             else

             {

                 map[i][j]=-;

                 if(s[]!='X')

                 {

                         int tp=(s[]-'')*+(s[]-'')*+s[]-'';

                         row[++row_num].x=i;

                         row[row_num].y=j;

                         row[row_num].val=tp;

                 }

                 if(s[]!= 'X' ) {

                         int tp = (s[]-'')*+(s[]-'')*+s[]-'';

                         col[++col_num].x = i;

                         col[col_num].y = j;

                         col[col_num].val = tp;

                     }

             }

         }

         T=emp+col_num+row_num+;

         st=;

         ed=T;

         Init();

         for(i=;i<=row_num;i++)

         {

             int pos = i;

             int x = row[i].x;

             int y = row[i].y;

             int cnt_len = ;

             for( y=y+; y <m ; y++ ) {

                 if( map[x][y] != - ) {

                     cnt_len++;

             Insert_Edge(i+, row_num+ map[x][y]+,);

                 } else break;

             }

             Insert_Edge(st,pos+,row[i].val-cnt_len);

         }

         for( i =  ; i <=col_num ; i++ ) {

             int pos =i++row_num+emp;

             int x = col[i].x;

             int y = col[i].y;

             int cnt_len = ;

             for( x=x+ ; x < n ; x++ ) {

                 if( map[x][y] != - ) {

                     cnt_len++;

             Insert_Edge(row_num+ map[x][y]+,pos,);

                 } else break;

             }

             Insert_Edge(pos,ed,col[i].val-cnt_len);

         }

         sap();

         for(i=;i<n;i++)

         {

         for(j=;j<m;j++)

         {

             if(map[i][j]==-)

             printf("_ ");

             else

             printf("%d ",print(map[i][j]));

         }

         printf("\n");

     }

     }

     return ;

 }

2015/5/26

kuangbin大法：

 /*

  * HDU 3338 Kakuro Extension

  * 题目意思就是在n*m的格子中，有黑白两种格子。要在白格子中填入数字1~9

  * 每一段横竖连续的白格子的和是知道的。

  * 求出一种满足的，保证有解。

  * 最大流。

  * 按照横竖段进行编号。然后行进列出，构造图形。

  *

  * 为了保证填入的数字是1~9，所以一开始每个格子减掉了1，相应的流入和流出都减掉。

  * 然后格子的边的赋值为8.

  * 还有就是要记录下相应边的编号，便于输出结果。

  *

  */

 #include <iostream>

 #include <string.h>

 #include <algorithm>

 #include <stdio.h>

 using namespace std;

 const int MAXN=;

 const int MAXM=;

 const int INF=0x3f3f3f3f;

 struct Node

 {

     int to,next,cap;

 }edge[MAXM];

 int tol;

 int head[MAXN];

 int gap[MAXN],dis[MAXN],pre[MAXN],cur[MAXN];

 void init()

 {

     tol=;

     memset(head,-,sizeof(head));

 }

 void addedge(int u,int v,int w,int rw=)

 {

     edge[tol].to=v;edge[tol].cap=w;edge[tol].next=head[u];head[u]=tol++;

     edge[tol].to=u;edge[tol].cap=rw;edge[tol].next=head[v];head[v]=tol++;

 }

 int sap(int start,int end,int nodenum)

 {

     memset(dis,,sizeof(dis));

     memset(gap,,sizeof(gap));

     memcpy(cur,head,sizeof(head));

     int u=pre[start]=start,maxflow=,aug=-;

     gap[]=nodenum;

     while(dis[start]<nodenum)

     {

         loop:

         for(int  &i=cur[u];i!=-;i=edge[i].next)

         {

             int v=edge[i].to;

             if(edge[i].cap&&dis[u]==dis[v]+)

             {

                 if(aug==-||aug>edge[i].cap)

                     aug=edge[i].cap;

                 pre[v]=u;

                 u=v;

                 if(v==end)

                 {

                     maxflow+=aug;

                     for(u=pre[u];v!=start;v=u,u=pre[u])

                     {

                         edge[cur[u]].cap-=aug;

                         edge[cur[u]^].cap+=aug;

                     }

                     aug=-;

                 }

                 goto loop;

             }

         }

         int mindis=nodenum;

         for(int i=head[u];i!=-;i=edge[i].next)

         {

             int v=edge[i].to;

             if(edge[i].cap&&mindis>dis[v])

             {

                 cur[u]=i;

                 mindis=dis[v];

             }

         }

         if((--gap[dis[u]])==)break;

         gap[dis[u]=mindis+]++;

         u=pre[u];

     }

     return maxflow;

 }

 char str[][][];

 int lx[][];//存横条的标号

 int ly[][];//存竖条的标号

 int num[];//记录lx,ly数组中出现的次数，因为题目要求填入的数字是1~9，所以先全部变1，相应的流要减少

 int id[][];//相应的边的编号，便于最后统计结果

 int main()

 {

     //freopen("in.txt","r",stdin);

     //freopen("out.txt","w",stdout);

     int n,m;

     while(scanf("%d%d",&n,&m)==)

     {

         for(int i=;i<n;i++)

             for(int j=;j<m;j++)

                 scanf("%s",str[i][j]);

         init();

         int tt=;//结点标号

         memset(lx,,sizeof(lx));

         memset(ly,,sizeof(ly));

         memset(num,,sizeof(num));

         for(int i=;i<n;i++)

             for(int j=;j<m;j++)

             {

                 if(strcmp(str[i][j],".......")!=)continue;

                 if(j== || lx[i][j-]==)lx[i][j]=++tt;

                 else lx[i][j]=lx[i][j-];

                 num[lx[i][j]]++;

             }

         for(int j=;j<m;j++)

             for(int i=;i<n;i++)

             {

                 if(strcmp(str[i][j],".......")!=)continue;

                 if(i== || ly[i-][j]==)ly[i][j]=++tt;

                 else ly[i][j]=ly[i-][j];

                 num[ly[i][j]]++;

             }

         int start=,end=tt+,nodenum=tt+;

         for(int i=;i<n;i++)

             for(int j=;j<m;j++)

                 if(strcmp(str[i][j],".......")==)

                 {

                     addedge(lx[i][j],ly[i][j],);

                     id[i][j]=tol-;//记录下来

                 }

         for(int i=;i<n;i++)

             for(int j=;j<m;j++)

             {

                 if(str[i][j][]!='\\')continue;

                 if(str[i][j][]!='X')

                 {

                     int tmp=(str[i][j][]-'')*+(str[i][j][]-'')*+(str[i][j][]-'');

                     if(ly[i+][j]!=)

                         addedge(ly[i+][j],end,tmp-num[ly[i+][j]]);

                 }

                 if(str[i][j][]!='X')

                 {

                     int tmp=(str[i][j][]-'')*+(str[i][j][]-'')*+(str[i][j][]-'');

                     if(lx[i][j+]!=)

                         addedge(start,lx[i][j+],tmp-num[lx[i][j+]]);

                 }

             }

         sap(start,end,nodenum);

         for(int i=;i<n;i++)

         {

             for(int j=;j<m;j++)

             {

                 if(j>)printf(" ");

                 if(strcmp(str[i][j],".......")!=)printf("_");

                 else printf("%c",''+-edge[id[i][j]].cap);

             }

             printf("\n");

         }

     }

     return ;

 }

最新文章

  1. Android 四大组件之Service
  2. 12.super关键字
  3. Cantor的数表
  4. xshell 通过ssh连接 ubuntu15_x64
  5. Loadrunner将字符串存为参数
  6. HTML学习笔记——head、body及简单标签
  7. .net利用NPOI导入导出Excel
  8. HTML5——地图应用
  9. win php nginx 配置小细节
  10. 杂谈之SolrCloud这个坑货
  11. Maven中Spring-Data-Redis存储对象(redisTemplate) （转）
  12. 用maven来创建web工程
  13. ruby和linux shell共同编程的示例
  14. PHP Excel使用方法
  15. html5 旋转导航练习
  16. 《Java大学教程》—第23章 Java网络编程
  17. BPM与OA的区别
  18. GDI+学习---2.GDI+编程模式及组成类
  19. 【Spring】20、使用TransactionSynchronizationManager在spring事务提交之后进行一些操作。
  20. virsh的详细命令解析（一）

热门文章

  1. Treats for the Cows 区间DP POJ 3186
  2. 关于Linux内核版本
  3. xshell5 优化方案
  4. 1.SpringBoot之Helloword 快速搭建一个web项目
  5. java 证书体系及应用,自已做https证书
  6. 洛谷P1782 旅行商的背包
  7. 洛谷P2458 保安站岗
  8. hihoCoder #1184 : 连通性二&#183;边的双连通分量（边的双连通分量模板）
  9. Java---容器基础总结
  10. 关于SQLserver的索引的一些脚本