[题解] LP2761 软件补丁问题

Author Avatar
空気浮遊 2018年02月09日
  • 在其它设备中阅读本文章
  • 网络流24题
  • 最短路
  • 位运算
  • 分享到 Facebook
  • 分享到 Telegram
  • 分享到 Twitter
  • 分享到微博

本题跟网络流没啥关系...
虽然我想用网络流做,但是并找不到网络流的题解 \_(:зゝ∠)_

Problem

自己去原 OJ 看

Solution

$2^{21}-1$ 个状态当节点。最短路:能否转移状态,以及转移之后的状态。这里要用位运算。
乱搞一阵。
自己想也行的。反正不难。

Code

// Code by ajcxsu
// Problem: LP2761

#include<bits/stdc++.h>
using namespace std;

int U;
const int N=1<<21,M=110;
struct Package{
    int req, ned;
    int clr, rep;
    Package() { req=ned=0, clr=U, rep=0; }
    bool idt(int x) {
        x&=req;
        if((x^ned)==0) return true;
        else return false;
    }
    int operator +(int x) {
        x&=clr;
        x|=rep;
        return x;
    }
} p[M];
int w[M];
int n,m;
int dist[N];

int main() {
    cin>>n>>m;
    U=(1<<n)-1;
    for(int i=1;i<=m;i++) {
        Package &np=p[i];
        np=Package();
        cin>>w[i];
        char ch;
        for(int j=0;j<n;j++) {
            cin>>ch;
            if(ch!='0') np.req|=1<<j;
            if(ch=='+') np.ned|=1<<j;
        }
        for(int j=0;j<n;j++) {
            cin>>ch;
            if(ch!='0') np.clr^=1<<j;
            if(ch=='+') np.rep|=1<<j;
        }
    }
    memset(dist,0x3f,sizeof(dist));
    queue<int> qu;
    dist[U]=0;
    qu.push(U);
    int na;
    while(!qu.empty()) {
        na=qu.front(), qu.pop();
        for(int i=1;i<=m;i++)
            if(p[i].idt(na) && dist[p[i]+na]>dist[na]+w[i]) {
                dist[p[i]+na]=dist[na]+w[i];
                qu.push(p[i]+na);
            }
    }
    if(dist[0]==0x3f3f3f3f) cout<<0<<endl;
    else cout<<dist[0]<<endl;
    return 0;
}

本文链接:https://pst.iorinn.moe/archives/sol_luogu_2761.html
许可: https://pst.iorinn.moe/license.html
若无特别说明,博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆

      新篇
旧篇      
    • fingerprint Login
  • home 主页
  • inbox 归档
    • December 2024 1
    • August 2024 1
    • June 2024 1
    • April 2024 3
    • March 2024 1
    • February 2024 2
    • January 2024 1
    • November 2023 1
    • August 2023 1
    • May 2023 1
    • February 2023 2
    • January 2023 2
    • July 2022 1
    • June 2022 1
    • April 2022 1
    • March 2022 1
    • February 2022 2
    • December 2021 1
    • November 2021 1
    • August 2021 3
    • July 2021 3
    • April 2021 2
    • March 2021 1
    • February 2021 4
    • January 2021 2
    • December 2020 1
    • November 2020 1
    • October 2020 3
    • September 2020 1
    • August 2020 1
    • July 2020 1
    • March 2020 1
    • December 2019 1
    • September 2019 1
    • July 2019 1
    • April 2019 2
    • March 2019 13
    • February 2019 15
    • January 2019 11
    • December 2018 3
    • November 2018 6
    • October 2018 28
    • September 2018 32
    • August 2018 19
    • July 2018 13
    • June 2018 27
    • May 2018 11
    • April 2018 12
    • March 2018 19
    • February 2018 8
    • January 2018 7
    • December 2017 2
    • November 2017 2
  • apps 分类
    • 笔记
    • 题解
    • 杂文
    • 技术
    • 游戏
    • 小说
  • 留言板
  • 关于
  • 友链
  • 文章总数 282
主题 - Material i
expand_less
Copyright © 2025 雪屋
Float in air.
Powered by Typecho
Theme - Material