【ACM】HDU 6611 K Subsequence 2019杭電多校第三場1009ネットワークフロー

7350 ワード

テーマリンク:http://acm.hdu.edu.cn/showproblem.php?pid=6611
K Subsequence
Time Limit：2000/2000 MS（Java/Others）メモリLimit：65536/65536 K（Java/Others）Total Submission（s）：2024 Acceepted Submission(s)：471
Problem Description
マスターQWsin is dating with Sinder.And now they are in a retaurant，the retaurant has n dishes in order.For each dish，it has a delicious value ai.However，they can only order k times.QWsin and Sinder have a special ordeng method，because they believe that by this way they can get maximm happiness value.Specificaly，for each order，they will chose a subsequence of dishes and in this subsequence，when i Now，master QWsin wants to know the maximm happiness value they can get but he thinks it's toeasuy，so he gives the problem to you.Can you answer his question？

Input
The re are multiple test cases.The first line of the input contains an integer T，indicating the number of test cases.For each test case:First line contains two positive integers n and k which are separated by spaces.second line contains n positive integer a 1,a 2,a 3…an represent the delicious value of each dish.1≦T≦5≦n≦2000 1≦k≦10≦ai≦1 e 5

Output
Only an integer represent the maximm happiness value they can get.

Sample Input

1 9 2 5 3 1 4 1 1 4 6

Sample Output

22

ソurce
2019 Multi-University Training Conteest 3

タイトルの大意:
n個の数の配列があります。ここからk個の重複しないサブシーケンスを取り出して、これらのシーケンスの権利値が最大となるように求めます。
考え方:
この問題はネットの流れと一番長くて、サブシーケンスの問題に似ています。図を作るときは、その問題の考え方を参考にしてもいいです。
1.各点iについては、2つの点i aとibに分割し、この2つの点の間に1つの容量を構築する。費用は-a[i]であり、この点は1回しか選択できないという意味で、選択したらa[i]が得られる（最大値を求めるので、費用は負である）
2.スーパーソースとシンクポイントを構築し、ソースからアジアに1つの容量を構築し、費用は0の辺で、ibから送金ポイントに1つの容量を構築し、費用は0の辺である。
3.i点とj点に対して、i点があれば
一番小さいのを走ればいいです。
この問題はspfaの板を使うことができなくて、タイムアウトすることができて、ネット上からdijkstra版の最小の費用の最大の流板を探して、参考だけに供します。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
typedef long long ll;
using namespace std;


#define MV 5000 //     
#define INF 0x3f3f3f3f


struct edge
{
    int t, cap, cost, rev;
    edge(int to = 0, int c = 0, int ct = 0, int r = 0): t(to), cap(c), cost(ct), rev(r) {};
};
vector  G[MV];//            ！                  G[i].clear();
int dis[MV];//   s          （         ）
int prevv[MV], preve[MV];//             
int h[MV];

//     Dijkstra  

//Dijkstra            ：

//h[MAX_V]:              O(FElogV)
typedef pairP;
int min_cost_flow(int v, int s, int t, int f) // main          
{

    int i, ans = 0;

    memset(h,0,sizeof h);

    while(f > 0)
    {
        //Dijkstra  ：      O(ElogV)
        priority_queue, greater
 > que;
        fill(dis, dis + v, INF);
        dis[s] = 0;
        que.push(P(0, s));
        while(!que.empty())
        {
            P p = que.top();
            que.pop();

            int v = p.second;
            if(dis[v] < p.first)
                continue;
            int size = G[v].size();

            for(i = 0; i < size; ++i)
            {
                edge es = G[v][i];//****
                if(es.cap > 0 && dis[es.t] > dis[v] + es.cost + h[v] - h[es.t])
                {

                    dis[es.t] = dis[v] + es.cost + h[v] - h[es.t];
                    prevv[es.t] = v;
                    preve[es.t] = i;
                    que.push(P(dis[es.t], es.t));
                }
            }
        }

        if(dis[t] == INF)
            return -1;
        //   
        for(i = 0; i < v; ++i)
            h[i] += dis[i];
        int d = f;
        for(i = t; i != s; i = prevv[i])
            d = min(d, G[prevv[i]][preve[i]].cap);
        ans += d * h[t];

        f -= d;

        for(i = t; i != s; i = prevv[i])
        {
            edge &es =  G[prevv[i]][preve[i]];
            es.cap -= d;
            G[i][es.rev].cap += d;
        }
    }

    return ans;
}


void addedge(int s1,int t1,int cap,int cost)
{
    G[s1].push_back(edge(t1, cap, cost, G[t1].size()));
    G[t1].push_back(edge(s1, 0, -cost, G[s1].size() - 1));
}

int a[MV];
int main()
{
//    int n, v, s, t, f;//n     
//                      // v      （       ）
//                      // s source  t sink
//                     // f        
    //freopen("in.txt","r",stdin);
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,k;
        scanf("%d%d",&n,&k);
        for(int i=1;i<=2*n+5;i++)
            G[i].clear();
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        int sp=0,tp=2*n+1;
        //addedge(sp,sp+1,k,0);
        for(int i=1;i<=n;i++)
        {
            addedge(2*i-1,2*i,1,-a[i]);
            addedge(sp,2*i-1,1,0);
            addedge(2*i,tp,1,0);
            for(int j=i+1;j<=n;j++)
            {
                if(a[j]>=a[i])
                    addedge(2*i,2*j-1,1,0);
            }
        }
        printf("%d
",-min_cost_flow(2*n+2,sp,tp,k));
    }
    return 0;
}

ps：一番長いサブシーケンスのコードを入れます。

#include
#include
#include
#include
using namespace std;
const int Ni = 1010;
const int MAX = 1<<26;
int a[Ni],dp[Ni];
struct Edge
{
    int u,v,c;
    int next;
} edge[20*Ni];
int n,m;
int edn;//  
int p[Ni];//  
int d[Ni];
int sp,tp;//  ，  

void addedge(int u,int v,int c)
{
    edge[edn].u=u;
    edge[edn].v=v;
    edge[edn].c=c;
    edge[edn].next=p[u];
    p[u]=edn++;

    edge[edn].u=v;
    edge[edn].v=u;
    edge[edn].c=0;
    edge[edn].next=p[v];
    p[v]=edn++;
}
int bfs()
{
    queue  q;
    memset(d,-1,sizeof(d));
    d[sp]=0;
    q.push(sp);
    while(!q.empty())
    {
        int cur=q.front();
        q.pop();
        for(int i=p[cur]; i!=-1; i=edge[i].next)
        {
            int u=edge[i].v;
            if(d[u]==-1 && edge[i].c>0)
            {
                d[u]=d[cur]+1;
                q.push(u);
            }
        }
    }
    return d[tp] != -1;
}
int dfs(int a,int b)
{
    int r=0;
    if(a==tp)return b;
    for(int i=p[a]; i!=-1 && r0 && d[u]==d[a]+1)
        {
            int x=min(edge[i].c,b-r);
            x=dfs(u,x);
            r+=x;
            edge[i].c-=x;
            edge[i^1].c+=x;
        }
    }
    if(!r)d[a]=-2;
    return r;
}

int dinic(int sp,int tp)
{
    int total=0,t;
    while(bfs())
    {
        while(t=dfs(sp,MAX))
            total+=t;
    }
    return total;
}
int main()
{
    int len=1;
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
        dp[i]=1;
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j

C〓HttpWebRequestはGET、POSTを使って結果の取得を要求します。

Android開発(10)