45 条题解

  • 2
    @ 2017-03-21 22:00:49

    本人题解:网络流+最大费用最大流+拆点
    因为要限制每个点经过次数,故需要将每一个点拆为两个点,分别管理入和出。
    从每个点的入到出连一条边容量1费用x,再连一条容量k费用0,表示取x的数只能选一次,再走过就不能取了。
    然后向右下建边,从当前出建到右下入,容量k费用0,表示可以走k次。
    源点到(1,1)入建边容量k费用0,表示可以走k次。
    (n,m)出到汇点建边容量k费用0,表示可以走k次。
    跑最大费用最大流,费用即为解。

    #include<algorithm>
    #include<iostream>
    #include<iomanip>
    #include<cstring>
    #include<cstdlib>
    #include<vector>
    #include<cstdio>
    #include<cmath>
    #include<queue>
    using namespace std;
    inline const int Get_Int() {
    int num=0,bj=1;
    char x=getchar();
    while(x<'0'||x>'9') {
    if(x=='-')bj=-1;
    x=getchar();
    }
    while(x>='0'&&x<='9') {
    num=num*10+x-'0';
    x=getchar();
    }
    return num*bj;
    }
    const int maxn=5005;
    struct Edge {
    int from,to,cap,flow,cost; //cap->容量 flow->流量 cost->费用
    };
    struct MinimumCost_MaximumFlow { //最小费用最大流
    int n,m;
    vector<Edge>edges;
    vector<int>G[maxn];
    int a[maxn]; //可改进量
    int path[maxn]; //增广路径
    int inque[maxn]; //是否在队列中
    int dist[maxn];
    void init(int n) {
    this->n=n;
    for(int i=0; i<n; i++)G[i].clear();
    edges.clear();
    }
    void AddEdge(int from,int to,int cap,int cost) {
    edges.push_back((Edge) {
    from,to,cap,0,cost
    });
    edges.push_back((Edge) { //反向边
    to,from,0,0,-cost
    });
    m=edges.size();
    G[from].push_back(m-2);
    G[to].push_back(m-1);
    }
    bool BellmanFord(int s,int t,int& flow,long long& cost) {
    for(int i=0; i<=n; i++)dist[i]=0x7fffffff/2;
    memset(inque,0,sizeof(inque));
    queue<int>Q;
    Q.push(s);
    dist[s]=0;
    inque[s]=1;
    path[s]=0;
    a[s]=0x7fffffff/2; //出发点流量无穷大
    while(!Q.empty()) {
    int Now=Q.front();
    inque[Now]=0;
    Q.pop();
    for(int i=0; i<G[Now].size(); i++) {
    Edge& e=edges[G[Now][i]]; //引用传边
    int Next=e.to;
    if(e.cap>e.flow&&dist[Next]>dist[Now]+e.cost) {
    dist[Next]=dist[Now]+e.cost;
    path[Next]=G[Now][i];
    a[Next]=min(a[Now],e.cap-e.flow); //来自的点的流量和容量的最小值
    if(!inque[Next]) {
    Q.push(Next);
    inque[Next]=1;
    }
    }
    }
    }
    if(dist[t]==0x7fffffff/2)return false; //无法到达终点 已无增广路
    flow+=a[t]; //记录总流量
    cost+=(long long)dist[t]*(long long)a[t]; //计算费用
    for(int Now=t; Now!=s; Now=edges[path[Now]].from) {
    edges[path[Now]].flow+=a[t];
    edges[path[Now]^1].flow-=a[t]; //^1在此取反边 奇数使其+1 偶数使其-1
    }
    return true;
    }
    int MaxFlow(int s,int t,long long& cost) {
    int flow=0;
    cost=0;
    while(BellmanFord(s,t,flow,cost)); //找到没有增广路
    return flow;
    }
    } mcmf;
    int n,m,k;
    int pos(int x,int y) {
    return (x-1)*m+y;
    }
    int main() {
    k=Get_Int();
    m=Get_Int();
    n=Get_Int();
    mcmf.init(n*m*2+5);
    for(int i=1; i<=n; i++)
    for(int j=1; j<=m; j++) {
    int x=Get_Int();
    mcmf.AddEdge(pos(i,j),n*m+pos(i,j),1,-x);
    mcmf.AddEdge(pos(i,j),n*m+pos(i,j),k,0);
    if(i<n)mcmf.AddEdge(n*m+pos(i,j),pos(i+1,j),k,0);
    if(j<m)mcmf.AddEdge(n*m+pos(i,j),pos(i,j+1),k,0);
    }
    mcmf.AddEdge(n*m*2+2,pos(1,1),k,0);
    mcmf.AddEdge(n*m+pos(n,m),n*m*2+3,k,0);
    long long cost=0;
    mcmf.MaxFlow(n*m*2+2,n*m*2+3,cost);
    printf("%lld\n",-cost);
    return 0;
    }

  • 1
    @ 2020-10-08 20:01:09
    #include <cmath>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <iomanip>
    #include <iostream>
    #include <algorithm>
    #include <vector>
    #include <deque>
    #include <set>
    #include <limits>
    #include <string>
    #include <sstream>
    #include <thread>
    using namespace std;
    
    namespace dts
    {
        typedef long long ll;
        
        double oo_min=(numeric_limits<double>::min)(),oo_max=(numeric_limits<double>::max)();
        
        struct network_flows
        {
            vector<ll> e;
            vector<ll> pre;
            vector<ll> vis;
            vector<vector<ll> > cw;
            vector<vector<ll> > ce;
            vector<double> f;
            vector<double> u;
            vector<vector<double> > c;
            vector<vector<double> > p;
            deque<ll> q;
            
            void clear_flow()
            {
                e.clear();
                pre.clear();
                vis.clear();
                f.clear();
                u.clear();
            }
            
            void clear_edge()
            {
                clear_flow();
                cw.clear();
                ce.clear();
                c.clear();
                p.clear();
            }
            
            ll size()
            {
                return cw.size();
            }
            
            void set_size(ll size_v)
            {
                clear_edge();
                cw.resize(size_v);
                ce.resize(size());
                c.resize(size());
                p.resize(size());
            }
            
            void add_edge(ll x,ll y,double c_v,double p_v)
            {
                cw[x].push_back(y);
                c[x].push_back(c_v);
                p[x].push_back(p_v);
                ce[y].push_back(cw[x].size()-1);
                cw[y].push_back(x);
                c[y].push_back(0);
                p[y].push_back(-p_v);
                ce[x].push_back(cw[y].size()-1);
            }
            
            void prepare(ll s,ll t)
            {
                clear_flow();
                f.resize(size(),0);
                f[s]=oo_max;
                e.resize(size(),-1);
                u.resize(size(),oo_max);
                u[s]=0;
                pre.resize(size(),-1);
                pre[s]=s;
                vis.resize(size(),0);
            }
            
            ll bfs(ll s,ll t,double &flow,double &cost)
            {
                prepare(s,t);
                for (q.clear(),vis[s]=1,q.push_back(s);!q.empty();vis[q.front()]=0,q.pop_front())
                {
                    ll now=q.front();
                    for (ll i=0;i<cw[now].size();i++)
                        if (c[now][i]>0&&u[now]+p[now][i]<u[cw[now][i]])
                        {
                            f[cw[now][i]]=min(c[now][i],f[now]);
                            e[cw[now][i]]=i;
                            u[cw[now][i]]=u[now]+p[now][i];
                            pre[cw[now][i]]=now;
                            if (vis[cw[now][i]]==0)
                                vis[cw[now][i]]=1,q.push_back(cw[now][i]);
                        }
                }
                flow=f[t];
                cost=u[t];
                return (pre[t]!=-1);
            }
            
            void min_cost_max_flow(ll s,ll t,ll typ,double &flow,double &cost)
            {
                double temp_flow,temp_cost;
                while (bfs(s,t,temp_flow,temp_cost))
                {
                    for (ll i=t;i!=s;i=pre[i])
                        c[pre[i]][e[i]]-=temp_flow,c[i][ce[pre[i]][e[i]]]+=temp_flow;
                    flow+=temp_flow;
                    if (typ==0)
                        cost+=temp_cost;
                    else if (typ==1)
                        cost+=(temp_flow*temp_cost);
                }
            }
        };
        
        ll n,M,N;
        
        ll number(ll x,ll y)//max:N,M
        {
            return (x-1)*M+y;
        }
        
        void main()
        {
            while (~scanf("%lld%lld%lld",&n,&M,&N))
            {
                network_flows game;
                game.set_size(2+2*M*N);
                game.add_edge(0,number(1,1),n,0);
                game.add_edge(number(N,M)+N*M,game.size()-1,n,0);
                for (ll i=1;i<=N;i++)
                    for (ll j=1;j<=M;j++)
                    {
                        if (i>1)
                            game.add_edge(number(i-1,j)+N*M,number(i,j),n,0);
                        if (j>1)
                            game.add_edge(number(i,j-1)+N*M,number(i,j),n,0);
                        double v;
                        scanf("%lf",&v);
                        game.add_edge(number(i,j),number(i,j)+N*M,1,-v);
                        game.add_edge(number(i,j),number(i,j)+N*M,n-1,0);
                    }
                double c=0,p=0;
                game.min_cost_max_flow(0,game.size()-1,1,c,p);
                printf("%.0lf\n",-p);
            }
        }
    };
    
    int main(int argv,const char *argc[])
    {
        dts::main();
    }
    
  • 0
    @ 2015-10-26 17:18:07

    #include <stdio.h>
    #include <stdlib.h>

    #define NIL -1
    #define INF 10000000
    #define MIN(a,b) ((a)<(b)?(a):(b))

    typedef struct{
    int next;
    int from, to, value, f;
    } edge;

    edge E[200000];
    int headIndex[20000];
    int size = 0;

    short used[20000];
    int queue[200000];
    int dist[20000];
    int prev[20000];

    void addEdge1(int from, int to, int value, int capacity);
    void addEdge(int from, int to, int value, int capacity);
    int maxPath(int source, int sink, int numV);
    int maxValueFlow(int source, int sink, int numV);

    int main(){
    int height, width, maxCapacity, numV;
    int x, y, source, sink, value;

    scanf("%d %d %d", &maxCapacity, &width, &height);

    /*initialize*/
    for(x=0; x<20000; x++)
    headIndex[x] = NIL;

    /*build the network*/
    numV = 0;
    for(x=0; x<height; x++){
    for(y=0; y<width; y++){
    scanf("%d", &value);
    addEdge(numV, numV+1, value, 1); //connect numV & numV+1
    addEdge(numV, numV+1, 0, maxCapacity);
    if(x < height-1)
    addEdge(numV+1, numV+2*width, 0, maxCapacity); //connnect numV+1 & its downer neighbour, if exists
    if(y < width-1)
    addEdge(numV+1, numV+2, 0, maxCapacity); //connnect numV+1 & its righter neighbour, if exists
    numV += 2;
    }
    }
    source = numV, sink = numV+1;
    addEdge(source, 0, 0, maxCapacity); //source
    addEdge(numV-1, sink, 0, maxCapacity); //sink

    /*solve*/
    printf("%d\n", maxValueFlow(source, sink, numV+2));
    return 0;
    }
    void addEdge1(int from, int to, int value, int capacity){
    E[size].from = from;
    E[size].to = to;
    E[size].value = value;
    E[size].f = capacity;
    E[size].next = headIndex[from];
    headIndex[from] = size;
    size++;
    }
    void addEdge(int from, int to, int value, int capacity){
    addEdge1(from, to, value, capacity);
    addEdge1(to, from, -value, 0);
    }
    int maxPath(int source, int sink, int numV){
    int i, head = 0, tail = 0;
    for(i=0; i<numV; i++){
    used[i] = 0;
    prev[i] = NIL;
    dist[i] = -INF;
    }
    dist[source] = 0;
    queue[tail++] = source;
    while(head < tail){
    source = queue[head];
    used[source] = 0;
    i = headIndex[source];
    while(i != NIL){
    if(E[i].f > 0 && dist[E[i].to] < dist[source] + E[i].value){
    dist[E[i].to] = dist[source] + E[i].value;
    prev[E[i].to] = i;
    if(!used[E[i].to]){
    queue[tail++] = E[i].to;
    used[E[i].to] = 1;
    }
    }
    i = E[i].next;
    }
    head++;
    }
    return dist[sink];
    }
    int maxValueFlow(int source, int sink, int numV){
    int path, v, augment, value, ret = 0;
    while((value = maxPath(source, sink, numV)) > 0){
    augment = INF;
    for(v=sink; v!=source; ){
    path = prev[v];
    augment = MIN(augment, E[path].f);
    v = E[path].from;
    }
    for(v=sink; v!=source; ){
    path = prev[v];
    E[path].f -= augment;
    E[path^1].f += augment;
    v = E[path].from;
    }
    ret += value*augment;
    }
    return ret;
    }

  • 0
    @ 2015-10-22 17:37:29

    费用流来写这题是沙茶题(大雾)
    然而我前两次一不小心写错ORZORZ
    膜拜DP的神犇
    没能秒过
    编译成功

    foo.cpp: In function 'bool SPFA(int&)':
    foo.cpp:94:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(i = 0;i < G[x].size();i ++) {
    ^
    测试数据 #0: Accepted, time = 5 ms, mem = 2932 KiB, score = 10
    测试数据 #1: Accepted, time = 4 ms, mem = 2932 KiB, score = 10
    测试数据 #2: Accepted, time = 15 ms, mem = 3004 KiB, score = 10
    测试数据 #3: Accepted, time = 6 ms, mem = 2948 KiB, score = 10
    测试数据 #4: Accepted, time = 15 ms, mem = 2932 KiB, score = 10
    测试数据 #5: Accepted, time = 3 ms, mem = 2924 KiB, score = 10
    测试数据 #6: Accepted, time = 0 ms, mem = 2928 KiB, score = 10
    测试数据 #7: Accepted, time = 2 ms, mem = 2932 KiB, score = 10
    测试数据 #8: Accepted, time = 15 ms, mem = 2928 KiB, score = 10
    测试数据 #9: Accepted, time = 15 ms, mem = 2940 KiB, score = 10
    Accepted, time = 80 ms, mem = 3004 KiB, score = 100
    代码:
    #include <iostream>
    #include <queue>
    #include <cstring>
    #include <cstdio>
    #include <vector>
    #define MAXN 23000
    #define INF 0x3f3f3f3f
    using namespace std;

    struct Edge {
    int u, v, cap, cost;
    } edge[110000];

    int rep, N, M, ecnt;
    int inq[MAXN];
    queue<int> Q;
    int d[MAXN];
    int p[MAXN];
    int a[MAXN];
    int mat[110][110];
    vector<int> G[MAXN];
    int wx[2] = {0, 1};
    int wy[2] = {1, 0};
    int S, T;

    inline void add(int u, int v, int cap, int cost) {
    edge[ecnt].u = u;
    edge[ecnt].v = v;
    edge[ecnt].cap = cap;
    edge[ecnt].cost = cost;
    G[u].push_back(ecnt ++);
    edge[ecnt].u = v;
    edge[ecnt].v = u;
    edge[ecnt].cap = 0;
    edge[ecnt].cost = -cost;
    G[v].push_back(ecnt ++);
    }

    inline void in() {
    int i, j;
    scanf("%d%d%d", &rep, &M, &N);
    for(i = 0;i < N;i ++) {
    for(j = 0;j < M;j ++) {
    scanf("%d", &mat[i][j]);
    }
    }
    }

    inline bool is_in(int x, int y) {
    if(x >= 0 && x < N && y >= 0 && y < M) return 1;
    return 0;
    }

    inline int pos(int x, int y, int flg) {
    return x * M + y + flg * N * M;
    }

    inline void build() {
    int i, j, k;
    S = 21997, T = 21998;
    for(i = 0;i < N;i ++) {
    for(j = 0;j < M;j ++) {
    add(pos(i, j, 0), pos(i, j, 1), 1, -mat[i][j]);
    add(pos(i, j, 0), pos(i, j, 1), INF, 0);
    for(k = 0;k < 2;k ++) {
    int tx = i + wx[k], ty = j + wy[k];
    if(is_in(tx, ty)) {
    add(pos(i, j, 1), pos(tx, ty, 0), rep, 0);
    }
    }
    }
    }
    add(S, pos(0, 0, 0), rep, 0);
    add(pos(N - 1, M - 1, 1), T, INF, 0);
    }

    inline int min(int a, int b) { return a > b ? b : a; }

    bool SPFA(int& cost) {
    int i;
    memset(inq, 0, sizeof(inq));
    //memset(a, 0x3f, sizeof(a));
    memset(d, 0x3f, sizeof(d));
    //memset(p, 0, sizeof(p));
    Q.push(S);
    inq[S] = 1;
    d[S] = 0;
    a[S] = INF;
    p[S] = 0;
    while(!Q.empty()) {
    int x = Q.front();
    Q.pop();
    inq[x] = 0;
    for(i = 0;i < G[x].size();i ++) {
    Edge& e = edge[G[x][i]];
    if(e.cap > 0 && d[e.v] > d[x] + e.cost) {
    d[e.v] = d[x] + e.cost;
    a[e.v] = min(a[x], e.cap);
    p[e.v] = G[x][i];
    if(!inq[e.v]) {
    inq[e.v] = 1;
    Q.push(e.v);
    }
    }
    }
    }
    if(d[T] == INF) return 0;
    cost += d[T];
    for(i = T;i != S;) {
    edge[p[i]].cap -= a[T];
    edge[p[i] ^ 1].cap += a[T];
    i = edge[p[i]].u;
    }
    return 1;
    }

    inline void solve() {
    int cost = 0;
    while(SPFA(cost));
    cout << -cost;
    }

    int main() {
    //freopen("in.txt", "r", stdin);
    in();
    build();
    solve();
    //while(1);
    return 0;
    }

  • 0
    @ 2015-01-31 23:20:13

    总是TLE第三个点咋回事???

  • 0
    @ 2014-04-19 13:06:22

    第三个点没能秒过,。

  • 0
    @ 2013-10-09 21:28:53

    费用流:
    编译成功

    测试数据 #0: Accepted, time = 0 ms, mem = 692 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 692 KiB, score = 10
    测试数据 #2: Accepted, time = 15 ms, mem = 1032 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 760 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 672 KiB, score = 10
    测试数据 #5: Accepted, time = 0 ms, mem = 664 KiB, score = 10
    测试数据 #6: Accepted, time = 0 ms, mem = 652 KiB, score = 10
    测试数据 #7: Accepted, time = 0 ms, mem = 668 KiB, score = 10
    测试数据 #8: Accepted, time = 0 ms, mem = 664 KiB, score = 10
    测试数据 #9: Accepted, time = 0 ms, mem = 708 KiB, score = 10
    Accepted, time = 15 ms, mem = 1032 KiB, score = 100
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    #include <queue>
    #include <cstdlib>

    using namespace std;

    #define MAXN 101
    #define MAXM 21
    #define MAXV MAXN*MAXM*2+10
    #define inf 0x7fffffff

    struct edge {
    int t,f,c;
    edge *pair,*next;
    edge () {
    pair=next=NULL;
    }
    } *head[MAXV];

    void Add(int s,int t,int f,int c) {
    edge *p=new(edge);
    p->t=t;
    p->f=f;
    p->c=c;
    p->next=head[s];
    head[s]=p;
    }

    void AddEdge(int s,int t,int f,int c) {
    Add(s,t,f,c);
    Add(t,s,0,-c);
    head[s]->pair=head[t];
    head[t]->pair=head[s];
    }

    int n,m,V=0,S,T,k;
    int v[MAXN][MAXM][2];
    int w[MAXN][MAXM];

    void INIT() {
    memset(head,0,sizeof(head));
    scanf("%d%d%d",&k,&m,&n);
    for (int i=0;i++<n;) {
    for (int j=0;j++<m;) {
    scanf("%d",&w[i][j]);
    v[i][j][0]=++V;v[i][j][1]=++V;
    AddEdge(v[i][j][0],v[i][j][1],1,-w[i][j]);
    AddEdge(v[i][j][0],v[i][j][1],inf,0);
    }
    }
    S=++V;T=S+1;
    AddEdge(S,v[1][1][0],k,0);
    AddEdge(v[n][m][1],T,k,0);
    for (int i=0;i++<n;) {
    for (int j=0;j++<m;) {
    if (i+1<=n) AddEdge(v[i][j][1],v[i+1][j][0],inf,0);
    if (j+1<=m) AddEdge(v[i][j][1],v[i][j+1][0],inf,0);
    }
    }
    }

    int d[MAXV];
    bool f[MAXV];
    queue<int>Q;

    void spfa() {
    for (int i=0;i++<T;) d[i]=inf;
    memset(f,true,sizeof(f));
    d[S]=0;
    while (!Q.empty()) Q.pop();
    Q.push(S);
    while (!Q.empty()) {
    int v=Q.front();
    Q.pop();
    if (!f[v]) continue;
    f[v]=false;
    for (edge *p=head[v];p;p=p->next) {
    if (p->f&&d[p->t]>d[v]+p->c) {
    d[p->t]=d[v]+p->c;
    f[p->t]=true;
    Q.push(p->t);
    }
    }
    }
    }

    int dist[MAXV],slack[MAXV];
    int cost=0;

    void dfs(int v) {
    f[v]=false;
    for (edge *p=head[v];p;p=p->next) {
    if (p->f&&d[v]+p->c==d[p->t]&&f[p->t]) {
    dist[p->t]=dist[v]-p->c;
    dfs(p->t);
    }
    }
    }

    int aug(int v,int flow) {
    if (v==T) {
    cost+=flow*(dist[S]-dist[T]);
    return flow;
    }
    f[v]=false;
    int rec=0;
    for (edge *p=head[v];p;p=p->next) {
    if (p->f&&f[p->t]) {
    if (dist[v]==dist[p->t]+p->c) {
    int ret=aug(p->t,min(flow-rec,p->f));
    p->f-=ret,p->pair->f+=ret;
    if ((rec+=ret)==flow) return flow;
    } else slack[p->t]=min(slack[p->t],dist[p->t]-dist[v]+p->c);
    }
    }
    return rec;
    }

    bool relabel() {
    int delta=inf;
    for (int i=0;i++<T;) {
    if (f[i]) delta=min(delta,slack[i]);
    }
    if (delta==inf) return false;
    for (int i=0;i++<T;) {
    if (!f[i]) dist[i]+=delta;
    }
    return true;
    }

    void costflow() {
    spfa();
    memset(f,true,sizeof(f));
    memset(dist,0,sizeof(dist));
    dfs(S);
    do {
    for (int i=0;i++<T;) slack[i]=inf;
    do {
    memset(f,true,sizeof(f));
    } while (aug(S,0x7fffffff));
    } while (relabel());
    }

    int main() {
    INIT();
    costflow();
    printf("%d\n",-cost);
    return 0;
    }

  • 0
    @ 2013-08-12 14:31:30

    错三个点。。。

  • 0
    @ 2010-04-11 11:21:31

    编译通过...├ 测试数据 01:答案正确...ms├ 测试数据 02:答案正确...ms├ 测试数据 03:答案正确...ms├ 测试数据 04:答案正确...ms├ 测试数据 05:答案正确...ms├ 测试数据 06:答案正确...ms├ 测试数据 07:答案正确...ms├ 测试数据 08:答案正确...ms├ 测试数据 09:答案正确...ms├ 测试数据 10:答案正确...msAccepted 有效得分:100 有效耗时:0ms

    网上的第一道费用流~

  • 0
    @ 2010-03-14 15:58:56

    Accepted 有效得分:100 有效耗时:0ms

    太感动了,第一道最大费用最大流一次AC啊 T^T

    编的好郁闷啊,活活拆了3个点出来,幸好用了邻接表……

    原来最大费用最大流真的只要把最小费用最大流SPFA的""就行了……

  • 0
    @ 2010-03-08 20:13:37

    这题费用流比动归好写多了,顺便让我把SPFA的费用流调对了…………

    做法很简单,就是费用流,建图不会的向下找就行了。

    另外这题到底有没DP算法??跪求神牛解答 Orz

  • 0
    @ 2010-02-28 20:12:44

    费用流,spfa+增广路

  • 0
    @ 2009-10-31 15:58:56

    为什么……

    网络流……

    欺负人……

    呜呜呜……

    我哭了……

    不做了……

    不活了……

  • 0
    @ 2009-10-23 19:38:13

    膜拜楼下的程序...

    长度是我的2.5倍...

  • 0
    @ 2009-10-12 20:42:54

    program problem;

    var

    en,et,ec,eu,ep,ex:Array[0..250000] of longint;

    dis:array[0..1000] of longint;

    v:array[0..1000] of boolean;

    i,j,k,n,m,w,cost,l:longint;

    a,b,ans,left,right:longint;

    function min(a,b:longint):longint;

    begin

    if a0)and not v[et[i]] and(dis[et[i]]+ec[i]=dis[no]) then

           begin

           d:=aug(et[i],min(m,eu[i]));

           if d>0 then

              begin

              dec(eu[i],d);

              inc(eu[ep[i]],d);

              ex[no]:=i;

              exit(d);

              end;

           end;

         i:=en[i];

         end;

       ex[no]:=i;

       exit(0);

    end;

    function modlabel:boolean;

    var

    d,i,j:longint;

    begin

       d:=maxlongint;

       for i:=1 to n do

         if v[i] then

           begin

           j:=en[i];

           while j0 do

              begin

              if (eu[j]>0)and not v[et[j]] and(ec[j]-dis[i]+dis[et[j]]0 do

         fillchar(v,sizeof(v),0);

    until modlabel;

    work:=cost;

    end;

    function solve(x,d:longint):longint;

    var i,k,t,p,last,cost,lk:longint;

    begin

    fillchar(en,sizeof(en),0);

    fillchar(dis,sizeof(dis),0);

    k:=0; n:=2; t:=x; p:=0;

    while x0 do

       begin

       k:=k+x mod 10;

       x:=x div 10;

       inc(p);

       end;

    n:=1; x:=t; l:=k+p+1; last:=1; cost:=1; lk:=0;

    while x0 do

       begin

       k:=x mod 10;

       for i:=1 to k do

         begin

         inc(n);

         build(last,n,1,-cost);

         build(n,last+k+1,1,0);

         end;

       cost:=cost*10;

       inc(n);

       if last1 then

         begin

         if lk

  • 0
    @ 2009-10-12 18:33:56

    ..在一群神牛光环的笼罩下。。终于猥琐的流过去了。。

    。。。交这道题的原因是3取方格数一直都动规不过去。。然后就只得写流了。。

    附上建图的代码,积德。。

    AddEdge(a,b,flow,cost);

    Pos(x,y,flag) flag == 0 是进去的边,flag == 1是出去的边

    for (int i = 0; i

  • 0
    @ 2009-10-05 13:33:51

    Dp: 太麻烦.

    流 :是个好东西!

  • 0
    @ 2009-10-03 15:13:30

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    还动态规划...沙茶的网络流!

  • 0
    @ 2009-10-01 20:00:20

    写完此题,桌角茶凉

  • 0
    @ 2009-09-27 09:56:24

    这个网络流解比较简单,动规很难啊!

信息

ID
1653
难度
5
分类
图结构 | 网络流动态规划 点击显示
标签
递交数
420
已通过
135
通过率
32%
被复制
3
上传者