結果

問題 No.1678 Coin Trade (Multiple)
ユーザー PCTprobability
提出日時 2021-09-10 21:55:59
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,641 bytes
コンパイル時間 5,699 ms
コンパイル使用メモリ 201,604 KB
最終ジャッジ日時 2025-01-24 10:28:25
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30 TLE * 26
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:93:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   93 |         scanf("%d %d",&N2,&K);
      |         ~~~~~^~~~~~~~~~~~~~~~

ソースコード

diff # 

//Intervals (POJ No.3680)
//Cost flow
#include<stdio.h>
#include<algorithm>
#include<queue>
#include <bits/stdc++.h>
using namespace std;
const int maxn=100000;
int T,N,K,N2;
int hashi[maxn];
int a[maxn];
int w[maxn];
struct edge
{
    int to;
    int from;
    int cost;
    int flow;
    int next;
    edge(){}
    edge(int from,int to,int cost,int flow,int next):from(from),to(to),cost(cost),flow(flow),next(next){}
};
edge n[maxn*10];
int cnt;
int len;
int now;
int head[maxn];
bool vis[maxn];
int dist[maxn];
int pre[maxn];
queue <int> q;
void insert(int x,int y,int z,int cost)
{
    n[++cnt]=edge(x,y,cost,z,head[x]);
    head[x]=cnt;
    n[++cnt]=edge(y,x,-cost,0,head[y]);
    head[y]=cnt;
    return ;
}
void SPFA(int s,int t)
{
    fill(dist,dist+maxn,110000);
    q.push(s);
    vis[s]=1;
    dist[s]=0;
    while(!q.empty())
    {
        now=q.front();
        q.pop();
        vis[now]=0;
        for(int i=head[now];i;i=n[i].next)
        {
            if(n[i].flow>0)
            {
                if(dist[n[i].to]>dist[now]+n[i].cost)
                {
                    dist[n[i].to]=dist[now]+n[i].cost;
                    pre[n[i].to]=i;
                    if(!vis[n[i].to])
                    {
                        vis[n[i].to]=1;
                        q.push(n[i].to);
                    }
                }
            }
        }
    }
    for(int i=pre[t];i;i=pre[n[i].from])
    {
        n[i].flow--;
        n[i^1].flow++;
    }
    return ;
}
int Mincost_flow(int s,int t,int num)
{
    int ans=0;
    while(num--)
    {
        SPFA(s,t);
        ans+=dist[t];
    }
    return -ans;
}
int main()
{
  T=1;
   // scanf("%d",&T);
    while(T--)
    {
        cnt=1;
        fill(head,head+maxn,0);
        scanf("%d %d",&N2,&K);
     vector<int> now(N2);
      int u=1;
      for(int i=0;i<N2;i++){
        int k;
        cin>>k;
        now[i]=k;
        int x;
        cin>>x;
        for(int j=0;j<x;j++){
          int y;
          cin>>y;
          N++;
          a[u*2-1]=y;
          a[u*2]=i+1;
          w[u]=now[i]-now[y-1];
          u++;
        }
      }
        for(int i=1;i<=N;i++)
        {
            hashi[i*2-1]=a[i*2-1];
            hashi[i*2]=a[i*2];
        }
        sort(hashi+1,hashi+2*N+1);
        len=unique(hashi+1,hashi+2*N+1)-hashi-1;
        for(int i=1;i<=N*2;i++)
        {
            a[i]=lower_bound(hashi+1,hashi+len+1,a[i])-hashi;
            if(!(i&1))insert(a[i-1],a[i],1,-w[i/2]);
        }
        for(int i=1;i<len;i++)insert(i,i+1,110000,0);
        insert(len,len+1,K,0);
        insert(0,1,K,0);
        printf("%d\n",Mincost_flow(0,len+1,K));
    }
}
0