【CF325C】Monsters and Diamonds

· · 题解

二合一傻逼题。没看到边权一定为正数，以为有 0 边搞 max 部分搞了半天...

事实上 min 部分感觉就是这题改一改，是一个 dij 基础题。

具体说就是我们设 f(i) 是一只怪物 i 能得到的最少钻石数量，然后转移就是枚举它的拆分方式，设得到怪物集合 S 和 n 颗钻石，那么取 n+\sum_{j\in S}f(j) 的最小值。

只要倒着跑最短路就行，就是每次确定一个怪物的 f 以后，枚举所有拆分方式包含它的拆分，如果它是该拆分最后一个确定 f 的怪物，那么这个拆分的 start（就是输入里每组拆分的第一个数）就可以被更新了。

容易发现这样能顺便跑出 -1 的信息。

然后 max 就很傻逼了，我们先把那些为 -1 的点忽略掉来看。然后每种拆分方式都至少得到一颗钻石，所以就很有意思，就是你不能出现环，具体地就是如果 a 拆到最后又来一只 a 那就 -2 了。

这个时候你可以缩点在 dag 上跑一个 dp。我本来这样写的结果最后弃了（）

考虑直接记忆化，搜到还在 dfs 栈中的点说明 -2，搜到已经明确答案是 -2 的点，也可以确定答案是 -2。否则，枚举所有拆分方式然后直接转移就行了。

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define op(x) ((x&1)?x+1:x-1)
#define odd(x) (x&1)
#define even(x) (!odd(x))
#define lc(x) (x<<1)
#define rc(x) (lc(x)|1)
#define lowbit(x) (x&-x)
#define Max(a,b) (a>b?a:b)
#define Min(a,b) (a<b?a:b)
#define next Cry_For_theMoon
#define il inline
#define pb(x) push_back(x)
#define is(x) insert(x)
#define sit set<int>::iterator
#define mapit map<int,int>::iterator
#define pi pair<int,int>
#define ppi pair<int,pi>
#define pp pair<pi,pi>
#define fr first
#define se second
#define vit vector<int>::iterator
#define mp(x,y) make_pair(x,y)
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef double db;
using namespace std;
const int MAXN=1e5+10,INF=1e9,LIM=3.14e8;
int m,n,l[MAXN],st[MAXN],cnt[MAXN],ins[MAXN];
map<int,int>occ[MAXN];
set<int>s1[MAXN],s2[MAXN];
int ans[MAXN][2];
vector<int>e1[MAXN],e2[MAXN],from[MAXN];
struct Node{
    int u,dis;
    bool operator<(const Node& n2)const{return dis>n2.dis;}
};
priority_queue<Node>q;
int vis[MAXN],dis[MAXN];
queue<int>qu;
void output();
int dfs(int u){
    vis[u]=1;
    if(ans[u][0]==-1)return ans[u][1]=ans[u][0]=-1;
    ins[u]=1;
    for(int idx:from[u]){
        //计划idx
        int ret=0,val,flag1=1,flag2=1;
        for(pi p:occ[idx]){
            int v=p.fr,w=p.se; //w个v
            if(ans[v][0]==-1){flag1=0;continue;}
            if(ins[v]){flag2=0;continue;}
            val=vis[v]?ans[v][1]:dfs(v);
            if(val==-2){flag2=0;continue;}
            ret=Min(LIM,ret+1ll*w*val);
        }
        if(!flag1)continue;
        if(!flag2){ins[u]=0;return ans[u][1]=-2;}
        ret=min(LIM,ret+cnt[idx]);
        ans[u][1]=max(ans[u][1],ret);
    }
    ins[u]=0;
    return ans[u][1];
}
int main(){
    scanf("%d%d",&m,&n);
    rep(i,1,m){
        int tmp;scanf("%d%d",&st[i],&l[i]);
        from[st[i]].pb(i);
        rep(j,1,l[i]){
            scanf("%d",&tmp);
            if(tmp==-1)cnt[i]++;
            else{
                occ[i][tmp]++;
                s1[tmp].is(i);
            }
        }
    }
    //calculate min
    rep(i,0,n)dis[i]=INF;
    rep(i,1,m){
        if(occ[i].size()==0){
            dis[st[i]]=min(dis[st[i]],cnt[i]);
            q.push(((Node){st[i],dis[st[i]]}));
        }
    }
    while(q.size()){
        Node tmp=q.top();q.pop();
        int u=tmp.u;if(vis[u])continue;
        vis[u]=1;
        for(int idx:s1[u]){
            int v=st[idx],w=cnt[idx];
            s2[idx].is(u);
            if(s2[idx].size()==occ[idx].size()){
                int sum=0;
                for(auto p:occ[idx]){
                    sum=min((ll)LIM,sum+1ll*p.se*dis[p.fr]);
                }
                sum=min(LIM,sum+w);
                if(dis[v]>sum){
                    dis[v]=sum;
                    q.push(((Node){v,dis[v]}));
                }
            }
        }
    }
    rep(i,1,n)if(dis[i]==INF)ans[i][0]=-1;else ans[i][0]=dis[i];
    //calculate max
    memset(vis,0,sizeof vis);
    rep(i,1,n){
        if(vis[i])continue;
        dfs(i);
    }
    output();
    return 0;
}
void output(){
    rep(i,1,n){
        if(ans[i][0]==-1)printf("-1 -1\n");
        else printf("%d %d\n",ans[i][0],ans[i][1]);
    }
}