【网络流24题】【LOJ6010】数字梯形(费用流)

            

problem

  • 给定一个n行的数字梯形,第一行有m个数字
  • 从第一行的每个数字开始往左下或右下移动到底,累加路径上的值
  • 求数字总和最大。

满足限制:
1、路径互不相交
2、路径仅在数字结点处相交
3、路径随意相交

solution

对于3个限制:
1、拆点,费用流
2、限制边, 费用流
3、费用流

注意数组记得开大,,,是n行,不是n个。。。

codes

#include
#include
#include
#include
using namespace std;

const int N = 1100*2+10, M = 100000+10, inf = 1<<30;

//Grape
struct Edge{
    int from, to, cap, flow, cost;
}e[M];
int tot=1, head[N], Next[M];
void AddEdge(int u, int v, int w, int c){
    //正向边,初始容量w,单位费用c
    e[++tot].from = u, e[tot].to = v, e[tot].cap = w, e[tot].flow = 0, e[tot].cost = c;
    Next[tot] = head[u], head[u] = tot;
    //反向边,初始容量0,单位费用-c,与正向边成对存储
    e[++tot].from = v, e[tot].to = u, e[tot].cap = 0, e[tot].flow = 0, e[tot].cost = -c;
    Next[tot] = head[v], head[v] = tot;
}

//Cost flow
int s, t, incf[N], pre[N];
int dist[N], vis[N];
bool spfa(int &fl, int &cst){
    //spfa
    queue<int>q;
    memset(dist,0xcf,sizeof(dist));//-inf
    memset(vis,0,sizeof(vis));
    q.push(s); dist[s]=0; vis[s]=1;
    incf[s] = 1<<30; //到s为止的增广路上各边的最小的剩余容量
    while(q.size()){
        int x = q.front(); q.pop(); vis[x] = 0;
        for(int i = head[x]; i; i = Next[i]){
            if(e[i].flow==e[i].cap)continue; //剩余容量为0,不再残量网络中,不遍历
            int y = e[i].to;
            if(dist[y]//记录前驱,用于找方案
                if(!vis[y])vis[y]=1, q.push(y);
            }
        }
    }
    if(dist[t] == 0xcfcfcfcf)return false;//汇点不可达,已求出最大流
    //update
    int x = t;
    while(x != s){
        int i = pre[x];
        e[i].flow += incf[t];
        e[i^1].flow -= incf[t];
        x = e[i].from;
    }
    fl += incf[t];
    cst += dist[t]*incf[t];
    return true;
}
int maxflow(){
    int flow = 0, cost = 0;
    while(spfa(flow, cost));//,,,,,,
    return cost;
}

//Timu
int n, m, a[110][110];
void input(){
    cin>>m>>n;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= i+m-1; j++)
            cin>>a[i][j];
}
int code(int i, int j){
    return (m+m+i-2)*(i-1)/2+j;//梯形面积公式,一共这么多点。
}
void task1(){
    int num = code(n,n+m-1);//原先一共有这么多点
    s = 0, t = num*2+1;
    for(int i = 1; i <= m; i++)
        AddEdge(s,i,1,0);
    for(int i = 1; i <= n+m-1; i++)
        AddEdge(num+code(n,i),t,1,0);
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m+i-1; j++){
            AddEdge(code(i,j),num+code(i,j),1,a[i][j]);
            if(i < n){
                AddEdge(num+code(i,j),code(i+1,j),1,0);
                AddEdge(num+code(i,j),code(i+1,j+1),1,0);
            }
        }
    }
    cout<'\n';
}
void task2(){
    memset(head,0,sizeof(head));
    memset(Next,0,sizeof(Next));
    tot = 1;
    for(int i = 1; i <= m; i++)
        AddEdge(s,i,1,0);
    for(int i = 1; i <= n+m-1; i++)
        AddEdge(code(n,i),t,inf,a[n][i]);
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= i+m-1; j++){
            if(i < n){
                AddEdge(code(i,j),code(i+1,j), 1, a[i][j]);
                AddEdge(code(i,j),code(i+1,j+1), 1, a[i][j]);
            }
        }
    }
    cout<'\n';
}
void task3(){
    memset(head,0,sizeof(head));
    memset(Next,0,sizeof(Next));
    tot = 1;
    for(int i = 1; i <= m; i++)
        AddEdge(s,i,1,0);
    for(int i = 1; i <= n+m-1; i++)
        AddEdge(code(n,i),t,inf,a[n][i]);
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= i+m-1; j++){
            if(i < n){
                AddEdge(code(i,j),code(i+1,j), inf, a[i][j]);
                AddEdge(code(i,j),code(i+1,j+1), inf, a[i][j]);
            }
        }
    }
    cout<'\n';
}

int main(){
    ios::sync_with_stdio(false);
    input();
    task1();
    task2();
    task3();
    return 0;
}
点赞

发表评论

昵称和uid可以选填一个,填邮箱必填(留言回复后将会发邮件给你)
tips:输入uid可以快速获得你的昵称和头像