[kuangbin带你飞]专题十一 网络流

2022-10-13 19:52:13

 
 
   
ID
Origin
Title
  34 / 81 Problem A POJ 3436 ACM Computer Factory
  92 / 195 Problem B POJ 3281 Dining
  55 / 148 Problem C POJ 1087 A Plug for UNIX
  59 / 111 Problem D POJ 2195 Going Home
  44 / 132 Problem E POJ 2516 Minimum Cost
  35 / 72 Problem F POJ 1459 Power Network
  40 / 217 Problem G HDU 4280 Island Transport
  42 / 133 Problem H HDU 4292 Food
  34 / 90 Problem I HDU 4289 Control
  28 / 90 Problem J UVA 10480 Sabotage
  19 / 37 Problem K HDU 2732 Leapin' Lizards
  13 / 136 Problem L HDU 3338 Kakuro Extension
  36 / 358 Problem M HDU 3605 Escape
  17 / 58 Problem N HDU 3081 Marriage Match II
  15 / 61 Problem O HDU 3416 Marriage Match IV
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

34 / 81 Problem A POJ 3436 ACM Computer Factory

没懂。。

此题是最大流问题。题目意思比较难懂。
看得比较纠结。
就是说有N台组装电脑的机器。电脑的组成部分共有P部分。
每台机器有P个输入输出规格。还有一个容量Q；

其中输入规格有三种情况：0,1,2

0：该部分不能存在

1：该部分必须保留

2：该部分可有可无

输出规格有2种情况：0,1

0：该部分不存在

1：该部分存在

要求的是生产电脑最大的台数，就是求网络中的最大流。

这相当于是生产线。需要自己去建图。

但是考虑到每台机器都有容量，所以把一台机器分成两个点，中间建一条容量的边。

同时如果一台机器的输出符合另一台机器的输入，则建一条容量无穷大的边。

同时要增加源点和汇点。输入没有1的连接源点，输出全部是1的连接汇点。

92 / 195 Problem B POJ 3281 Dining

本题能够想到用最大流做，那真的是太绝了。建模的方法很妙！
题意就是有N头牛，F个食物，D个饮料。
N头牛每头牛有一定的喜好，只喜欢几个食物和饮料。
每个食物和饮料只能给一头牛。一头牛只能得到一个食物和饮料。
而且一头牛必须同时获得一个食物和一个饮料才能满足。问至多有多少头牛可以获得满足。
最初相当的是二分匹配。但是明显不行，因为要分配两个东西，两个东西还要同时满足。
最大流建图是把食物和饮料放在两端。一头牛拆分成两个点，两点之间的容量为1.喜欢的食物和饮料跟牛建条边，容量为1.
加个源点和汇点。源点与食物、饮料和汇点的边容量都是1，表示每种食物和饮料只有一个。
这样话完全是最大流问题了，。

/*

POJ 3281 最大流

//源点-->food-->牛(左)-->牛(右)-->drink-->汇点

//精髓就在这里，牛拆点，确保一头牛就选一套food和drink的搭配

*/

#include<stdio.h>

#include<iostream>

#include<string.h>

#include<algorithm>

#include<queue>

using namespace std;

//****************************************************

//最大流模板

//初始化：g[][],start,end

//******************************************************

const int MAXN=;

const int INF=0x3fffffff;

int g[MAXN][MAXN];//存边的容量，没有边的初始化为0

int path[MAXN],flow[MAXN],start,end;

int n;//点的个数，编号0-n.n包括了源点和汇点。

queue<int>q;

int bfs()

{

    int i,t;

    while(!q.empty())q.pop();//把清空队列

    memset(path,-,sizeof(path));//每次搜索前都把路径初始化成-1

    path[start]=;

    flow[start]=INF;//源点可以有无穷的流流进

    q.push(start);

    while(!q.empty())

    {

        t=q.front();

        q.pop();

        if(t==end)break;

        //枚举所有的点，如果点的编号起始点有变化可以改这里

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

        {

            if(i!=start&&path[i]==-&&g[t][i])

            {

                flow[i]=flow[t]<g[t][i]?flow[t]:g[t][i];

                q.push(i);

                path[i]=t;

            }

        }

    }

    if(path[end]==-)return -;//即找不到汇点上去了。找不到增广路径了

    return flow[end];

}

int Edmonds_Karp()

{

    int max_flow=;

    int step,now,pre;

    while((step=bfs())!=-)

    {

        max_flow+=step;

        now=end;

        while(now!=start)

        {

            pre=path[now];

            g[pre][now]-=step;

            g[now][pre]+=step;

            now=pre;

        }

    }

    return max_flow;

}

int main()

{

    int N,F,D;

    while(scanf("%d%d%d",&N,&F,&D)!=EOF)

    {

        memset(g,,sizeof(g));

        n=F+D+*N+;

        start=;

        end=n;

        for(int i=;i<=F;i++)g[][i]=;

        for(int i=F+*N+;i<=F+*N+D;i++)g[i][n]=;

        for(int i=;i<=N;i++)g[F+*i-][F+*i]=;

        int k1,k2;

        int u;

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

        {

            scanf("%d%d",&k1,&k2);

            while(k1--)

            {

                scanf("%d",&u);

                g[u][F+*i-]=;

            }

            while(k2--)

            {

                scanf("%d",&u);

                g[F+*i][F+*N+u]=;

            }

        }

        printf("%d\n",Edmonds_Karp());

    }

    return ;

}

55 / 148 Problem C POJ 1087 A Plug for UNIX

题意：在一个房间里有N种插座和使用M种插座的电器，，这M种插座有些在现有的插座中不包含，不过可以通过适配器来转化，有K种类型的适配器来转化，让你求最少会有多少电器没法使用插座。

思路:最大二分匹配。即求出最多有多少电器有相应的插座，然后用M减去就是所求，不过建图有点难想，我也是看了别人的解题报告才明白的。将电器和相应的插座类型连接起来，将能相互转化的插座连接起来，然后将不能直接使用N种插座而通过适配器的转换就能用的电器和插座连起来，然后就是求M种电器和Ｎ种插座的最大匹配了。呃，其实看到很多博客都是用最大流做的，原本这题也是在最大流的练习中找到的，但是我发现最大匹配更好理解，而且二分匹配加上源点和汇点就能转化成最大流。

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#include <iostream>

#include <algorithm>

#include <map>

#include <string>

#define  N 505

using namespace std ;

map<string , int>p ;

int mp[N][N] ;

int n , m , k , nx ;

int f[N] , d[N] ;

int dfs( int x )

{

    int i ;

    for ( i = m + ; i <= m + nx ; i++ )

    {

        if ( !f[i] && mp[x][i] )

        {

            f[i] =  ;

            if ( !d[i] || dfs( d[i] ))

            {

                d[i] = x ;

                return  ;

            }

        }

    }

    return  ;

}

//二分匹配模板

int floyd( )

{

    int i , sum ;

    sum =  ;

    memset( d ,  , sizeof ( d ));

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

    {

        memset( f ,  , sizeof ( f ));

        if ( dfs( i ))

        sum++;

    }

    return sum ;

}

int main()

{

    int i , j , t ;

    string str1 , str2 ;

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

    //输入N种插座

    scanf ( "%d" , &n ) ;

    p.clear();

    nx = n ;

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

    {

        cin>>str1 ;

        p[str1] = i ;

    }

    //输入M种电器

    scanf ( "%d" , &m );

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

    {

        cin>>str1>>str2 ;

        if ( p[str2] !=  )

        {

            int x = p[str2] ;

            mp[i][x+m] =  ;

        }

        else

        {

            n++ ;

            p[str2] = n ;

            mp[i][n+m] =  ;

        }

    }

    //输入K种转化关系

    scanf ( "%d" , &k );

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

    {

        cin>>str1>>str2 ;

        if ( p[str1] ==  )

        {

            n++ ;

            p[str1] = n ;

        }

        if ( p[str2] ==  )

        {

            n++ ;

            p[str2] = n ;

        }

        mp[p[str1]+m][p[str2]+m] =  ;

    }

    //将通过适配器可以使用原来N种插座的电器连起来。

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

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

    for ( t =  ; t <= m + n ; t++ )

    if ( mp[j][i] && mp[i][t] && !mp[j][t] )

    mp[j][t] =  ;

    int flow = floyd( );

    printf ( "%d\n" , m - flow ) ;

    return ;

}

最大流代码

#include<stdio.h>

#include<map>

#include<iostream>

#include<string.h>

#include<string>

#include<queue>

using namespace std;

//****************************************************

//最大流模板

//初始化：g[][],start,end

//******************************************************

const int MAXN=;

const int INF=0x3fffffff;

int g[MAXN][MAXN];//存边的容量，没有边的初始化为0

int path[MAXN],flow[MAXN],start,end;

int n;//点的个数，编号0-n.n包括了源点和汇点。

queue<int>q;

int bfs()

{

    int i,t;

    while(!q.empty())q.pop();//把清空队列

    memset(path,-,sizeof(path));//每次搜索前都把路径初始化成-1

    path[start]=;

    flow[start]=INF;//源点可以有无穷的流流进

    q.push(start);

    while(!q.empty())

    {

        t=q.front();

        q.pop();

        if(t==end)break;

        //枚举所有的点，如果点的编号起始点有变化可以改这里

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

        {

            if(i!=start&&path[i]==-&&g[t][i])

            {

                flow[i]=flow[t]<g[t][i]?flow[t]:g[t][i];

                q.push(i);

                path[i]=t;

            }

        }

    }

    if(path[end]==-)return -;//即找不到汇点上去了。找不到增广路径了

    return flow[end];

}

int Edmonds_Karp()

{

    int max_flow=;

    int step,now,pre;

    while((step=bfs())!=-)

    {

        max_flow+=step;

        now=end;

        while(now!=start)

        {

            pre=path[now];

            g[pre][now]-=step;

            g[now][pre]+=step;

            now=pre;

        }

    }

    return max_flow;

}

map<string,int>hash;

int main()

{

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

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

    string str1,str2;

    int N,M;

    int tol;

    while(scanf("%d",&N)!=EOF)

    {

        hash.clear();

        memset(g,,sizeof(g));

        start=;

        end=;

        tol=;

        while(N--)

        {

            cin>>str1;

            hash[str1]=tol;

            g[][tol]=;

            tol++;

        }

        scanf("%d",&M);

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

        {

            cin>>str1>>str2;

            if(hash[str1]==)hash[str1]=tol++;

            if(hash[str2]==)hash[str2]=tol++;

            g[hash[str1]][end]=;

            g[hash[str2]][hash[str1]]=;

        }

        scanf("%d",&N);

        while(N--)

        {

            cin>>str1>>str2;

            if(hash[str1]==)hash[str1]=tol++;

            if(hash[str2]==)hash[str2]=tol++;

            g[hash[str2]][hash[str1]]=INF;

        }

        n=tol-;

        printf("%d\n",M-Edmonds_Karp());

    }

    return ;

}

59 / 111 Problem D POJ 2195 Going Home

hint.做过的题，解题报告见以前博客

44 / 132 Problem E POJ 2516 Minimum Cost

hint.做过的题，解题报告见以前博客

35 / 72 Problem F POJ 1459 Power Network

hint.做过的题，解题报告见以前博客

40 / 217 Problem G HDU 4280 Island Transport

题意：有N个岛屿之间有M双向条路，每条路每个小时最多能通过C个人，现在问一个小时内，最多能把多少个顾客从最西边的岛屿送至最东边的岛屿上。

思路：网络流，求最大流。建图：每条路连接的两个岛屿之间建立一条容量为C的双向边，取超级源点与汇点，源点与最西边的岛屿，汇点与最东边的岛屿建立一条流量为无穷大的边。

/*

最大流模板

sap

*/

#include<stdio.h>

#include<string.h>

#include<algorithm>

#include<iostream>

using namespace std;

const int MAXN=;//点数的最大值

const int MAXM=;//边数的最大值

const int INF=0x3f3f3f3f;

struct Node

{

    int from,to,next;

    int cap;

}edge[MAXM];

int tol;

int head[MAXN];

int dep[MAXN];

int gap[MAXN];//gap[x]=y :说明残留网络中dep[i]==x的个数为y

int n;//n是总的点的个数，包括源点和汇点

void init()

{

    tol=;

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

}

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

{

    edge[tol].from=u;

    edge[tol].to=v;

    edge[tol].cap=w;

    edge[tol].next=head[u];

    head[u]=tol++;

    edge[tol].from=v;

    edge[tol].to=u;

    edge[tol].cap=;

    edge[tol].next=head[v];

    head[v]=tol++;

}

void BFS(int start,int end)

{

    memset(dep,-,sizeof(dep));

    memset(gap,,sizeof(gap));

    gap[]=;

    int que[MAXN];

    int front,rear;

    front=rear=;

    dep[end]=;

    que[rear++]=end;

    while(front!=rear)

    {

        int u=que[front++];

        if(front==MAXN)front=;

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

        {

            int v=edge[i].to;

            if(dep[v]!=-)continue;

            que[rear++]=v;

            if(rear==MAXN)rear=;

            dep[v]=dep[u]+;

            ++gap[dep[v]];

        }

    }

}

int SAP(int start,int end)

{

    int res=;

    BFS(start,end);

    int cur[MAXN];

    int S[MAXN];

    int top=;

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

    int u=start;

    int i;

    while(dep[start]<n)

    {

        if(u==end)

        {

            int temp=INF;

            int inser;

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

               if(temp>edge[S[i]].cap)

               {

                   temp=edge[S[i]].cap;

                   inser=i;

               }

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

            {

                edge[S[i]].cap-=temp;

                edge[S[i]^].cap+=temp;

            }

            res+=temp;

            top=inser;

            u=edge[S[top]].from;

        }

        if(u!=end&&gap[dep[u]-]==)//出现断层，无增广路

          break;

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

           if(edge[i].cap!=&&dep[u]==dep[edge[i].to]+)

             break;

        if(i!=-)

        {

            cur[u]=i;

            S[top++]=i;

            u=edge[i].to;

        }

        else

        {

            int min=n;

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

            {

                if(edge[i].cap==)continue;

                if(min>dep[edge[i].to])

                {

                    min=dep[edge[i].to];

                    cur[u]=i;

                }

            }

            --gap[dep[u]];

            dep[u]=min+;

            ++gap[dep[u]];

            if(u!=start)u=edge[S[--top]].from;

        }

    }

    return res;

}

int main()

{

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

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

    int start,end;

    int m;

    int u,v,z;

    int T;

    scanf("%d",&T);

    while(T--)

    {

        init();

        scanf("%d%d",&n,&m);

        int minx=;

        int maxx=-;

        int x,y;

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

        {

            scanf("%d%d",&x,&y);

            if(minx>x)

            {

                minx=x;

                start=i;

            }

            if(maxx<x)

            {

                maxx=x;

                end=i;

            }

        }

        while(m--)

        {

            scanf("%d%d%d",&u,&v,&z);

            addedge(u,v,z);

            addedge(v,u,z);

        }

        //n一定是点的总数，这是使用SAP模板需要注意的

        int ans=SAP(start,end);

        printf("%d\n",ans);

    }

    return ;

}

42 / 133 Problem H HDU 4292 Food

题意：有F种食物 D种饮料 它们都有一定的数量 有N个人 每个人都有自己喜欢吃的食物和饮料 （每个人至少要一种食物和饮料） 只有能满足他的要求时他才会接服务 求最大能满足多少人？
思路：网络流 建一超级源点 汇点 源点与食物相连 边权为其数量，汇点与饮料相连 边权也为其数量 把人分成两个点 之间的边权为1 每个人与之需要的食物和饮料相连 边权为1

/*

题意：F种食物和D种饮料，每种食物和饮料的数目也是固定的，总共有N位顾客，每位顾客都只吃喝固定种类的食品

饮料，问最多能满足多少为顾客。

题解：最大流+拆点；

建图：将每位顾客拆成两个点，同一顾客之间加入权值为1的有向边限制了只能是一位一位顾客来满足，再加入源点

来连接每一种食物，权值为该食物数量，然后根据顾客喜欢的食物连接顾客，权值为1，因为每位顾客只需1份食物饮

料，然后加入饮料结点并根据顾客喜好连接，权值同样为1，然后将饮料与汇点连接，权值为饮料的数目，最终求得

的最大流即为最多能满足的顾客。

*/

#include <cstdio>

#include <cstring>

#define EMAX 200000

#define VMAX 1005

const int INF = 0xfffffff;

int head[VMAX],dis[VMAX],cur[VMAX],gap[VMAX],pre[VMAX];

int EN;

struct edge

{

    int from,to;

    int weight;

    int next;

}e[EMAX];

void insert(int u,int v,int w)

{

    e[EN].to = v;

    e[EN].weight = w;

    e[EN].next = head[u];

    head[u] = EN++;

    e[EN].weight = ;

    e[EN].to = u;

    e[EN].next = head[v];

    head[v] = EN++;

}

int sap(int s,int t, int n)

{

    memset(dis,,sizeof(dis));

    memset(gap,,sizeof(gap));

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

        cur[i] = head[i];

    int u = pre[s];

    pre[s] = s;

    int ret = ;

    int temp = -;

    gap[] = n;

    bool flag;

    while(dis[s] < n)

    {

        flag = false;

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

        {

            int v = e[i].to;

            if(e[i].weight && dis[u] == dis[v] + )

            {

                if (temp == - || temp>e[i].weight)

                    temp = e[i].weight;

                pre[v] = u;

                u = v;

                if(v == t)

                {

                    ret += temp;

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

                    {

                        e[cur[u]].weight -= temp;

                        e[cur[u]^].weight += temp;

                    }

                    temp = -;

                }

                flag = true;

                break;

            }

        }

        if (flag)

            continue;

        int mindis = n;

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

        {

            int v = e[i].to;

            if(e[i].weight && mindis > dis[v])

            {

                cur[u] = i;

                mindis = dis[v];

            }

        }

        gap[dis[u]]--;

        if( gap[dis[u]] == )

            break;

        dis[u] = mindis+;

        gap[dis[u]]++;

        u = pre[u];

    }

    return ret;

}

int main(void)

{

    int n,f,d,t;

    char s[];

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

    {

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

        EN = ;

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

        {

            scanf("%d",&t);

            insert(,i,t);//源点加边

        }

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

        {

            scanf("%d",&t);

            insert(f+*n+i,f+*n+d+,t);//汇点加边

        }

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

            insert(f+i,f+n+i,);//拆点

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

        {

            scanf("%s",s+);

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

                if (s[j] == 'Y')

                    insert(j,f+i,);//顾客与食物加边

        }

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

        {

            scanf("%s",s+);

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

                if (s[j] == 'Y')

                    insert(f+n+i,f+*n+j,);//顾客与饮料加边

        }

        printf("%d\n",sap(,f+*n+d+,f+*n+d+));

    }

    return ;

}

34 / 90 Problem I HDU 4289 Control

成都赛区网络赛1002题。
一场网络赛两题最大流，用SAP模板可以秒掉。
//

/*

HDU 4289

G++  62ms  1888K

最大流

SAP

*/

#include<stdio.h>

#include<iostream>

#include<map>

#include<set>

#include<algorithm>

#include<string.h>

#include<stdlib.h>

using namespace std;

const int MAXN=;//点数的最大值

const int MAXM=;//边数的最大值

const int INF=0x3f3f3f3f;

struct Node

{

    int from,to,next;

    int cap;

}edge[MAXM];

int tol;

int head[MAXN];

int dep[MAXN];

int gap[MAXN];//gap[x]=y:说明残留网络中 dep[i]==x的个数为y

int n;//点的实际个数，一定是总的点的个数，包括源点和汇点

void init()

{

    tol=;

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

}

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

{

    edge[tol].from=u;

    edge[tol].to=v;

    edge[tol].cap=w;

    edge[tol].next=head[u];

    head[u]=tol++;

    edge[tol].from=v;

    edge[tol].to=u;

    edge[tol].cap=;

    edge[tol].next=head[v];

    head[v]=tol++;

}

void BFS(int start,int end)

{

    memset(dep,-,sizeof(dep));

    memset(gap,,sizeof(gap));

    gap[]=;

    int que[MAXN];

    int front,rear;

    front=rear=;

    dep[end]=;

    que[rear++]=end;

    while(front!=rear)

    {

        int u=que[front++];

        if(front==MAXN)front=;

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

        {

            int v=edge[i].to;

            if(edge[i].cap!=||dep[v]!=-)continue;

            que[rear++]=v;

            if(rear==MAXN)rear=;

            dep[v]=dep[u]+;

            ++gap[dep[v]];

        }

    }

}

int SAP(int start,int end)

{

    int res=;

    BFS(start,end);

    int cur[MAXN];

    int S[MAXN];

    int top=;

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

    int u=start;

    int i;

    while(dep[start]<n)

    {

        if(u==end)

        {

            int temp=INF;

            int inser;

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

               if(temp>edge[S[i]].cap)

               {

                   temp=edge[S[i]].cap;

                   inser=i;

               }

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

            {

                edge[S[i]].cap-=temp;

                edge[S[i]^].cap+=temp;

            }

            res+=temp;

            top=inser;

            u=edge[S[top]].from;

        }

        if(u!=end&&gap[dep[u]-]==)//出现断层，无增广路

          break;

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

           if(edge[i].cap!=&&dep[u]==dep[edge[i].to]+)

             break;

        if(i!=-)

        {

            cur[u]=i;

            S[top++]=i;

            u=edge[i].to;

        }

        else

        {

            int min=n;

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

            {

                if(edge[i].cap==)continue;

                if(min>dep[edge[i].to])

                {

                    min=dep[edge[i].to];

                    cur[u]=i;

                }

            }

            --gap[dep[u]];

            dep[u]=min+;

            ++gap[dep[u]];

            if(u!=start)

              u=edge[S[--top]].from;

        }

    }

    return res;

}

int main()

{

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

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

    int N,M;

    int u,v;

    int start;

    int end;

    while(scanf("%d%d",&N,&M)!=EOF)

    {

        init();

        scanf("%d%d",&start,&end);

        start=*start-;

        end=*end;

        n=*N;

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

        {

            scanf("%d",&u);

            addedge(*i-,*i,u);

            addedge(*i,*i-,u);

        }

        while(M--)

        {

            scanf("%d%d",&u,&v);

            addedge(*u,*v-,INF);

            addedge(*v,*u-,INF);//这里一定要注意

        }

        printf("%d\n",SAP(start,end));

    }

    return ;

}

28 / 90 Problem J UVA 10480 Sabotage

最大流

19 / 37 Problem K HDU 2732 Leapin' Lizards

最大流

13 / 136 Problem L HDU 3338 Kakuro Extension

很神奇的最大流的题目。很有意思。

题目意思就是在n*m的格子中，有黑白两种格子。要在白格子中填入数字1~9
* 每一段横竖连续的白格子的和是知道的。
* 求出一种满足的，保证有解。
* 最大流。
* 按照横竖段进行编号。然后行进列出，构造图形。
*
* 为了保证填入的数字是1~9，所以一开始每个格子减掉了1，相应的流入和流出都减掉。
* 然后格子的边的赋值为8.
* 还有就是要记录下相应边的编号，便于输出结果。

36 / 358 Problem M HDU 3605 Escape

这题一看题目是很简单的最大流。
但是数据好大，试了很多模板，都是TLE。
后来发现可以合并点，
因为m<=10.
所以用二进制记录。
在n个点中，如果是一样的就合并。
这样最多是1024+m+2个点。
 
但是这题还是很坑。。。。在HDU上用G++交无论如何都是TLE的。直接读入数据输出都是TLE.
改成C++就AC了。。。
 

17 / 58 Problem N HDU 3081 Marriage Match II

最大流+二分+并查集

15 / 61 Problem O HDU 3416 Marriage Match IV

这题就是求从A到B的最短路径的条数。

一条边只能经过一次。

先通过最短路去除掉没有用的边。

然后用一次最大流就是答案了。

从A和B分别出发求最短路dist1,dist2.

注意从B求得额时候要反向。

如果dist1[a]+dist2[b]+c==dist1[B].那么这条边就是有用的。。

我用的SPFA求最短路的。

上一篇：关于 Spring Security OAuth2 中 Feign 调用 Token 问题


下一篇：空间搜索（圆范围）中Geohash编码方案和网格编码方案对比探讨