147 条题解

  • 1
    @ 2018-02-26 19:41:43

    我是一只蒟蒻,说的不对欢迎大佬指正。

    似乎没有人提出,治病的时候不会用两次同一种药。

    证明:
    1.连着用两次同种药是赤裸裸的浪费。
    2.先用一次药,治好了某些病,过了一段时间又用了一次药。那么第一次的治疗是无效的,一段时间后再用药与先用一次药状态一样。

    #include<bits/stdc++.h>
    using namespace std;
    int ans=1e9;
    int n,m,a[110][110],q[(1<<12)+10];
    bool v[110];
    void search(int s,int f)//标准的剪枝dfs,具体参见下方某题解
    {
        if(s==0){
            if(f<ans) ans=f;
            return;
        }
        if(f>=ans) return;
        if(q[s]<=f) return;
        else q[s]=f; 
        int p=s;
        for(int t=0;t<m;t++) if(v[t]){//v[t]记录治病过程中此药是否用过
            v[t]=false;
            for(int i=0;i<n;i++){
                if(a[t][i]==-1) s|=(1<<i);
                if(a[t][i]==1 && s&(1<<i))
                    s^=(1<<i); 
            }
            if(s==0){
                v[t]=true;
                if(f+1<ans) ans=f+1;
                return;
            }
            search(s,f+1);
            v[t]=true;
            s=p;
        }
        return;
    }
    int main()
    {
        scanf("%d",&n);
        scanf("%d",&m);
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                scanf("%d",&a[i][j]);
            }
        }
        memset(v,true,sizeof(v));
        memset(q,127,sizeof(q));
        search((1<<(n))-1,0);
        if(ans>0&&ans<1e6)
            printf("%d\n",ans);
        else printf("The patient will be dead.\n");
        return 0;
    }
    
  • 1
    @ 2017-05-07 12:57:21
    /*
    数据是不是太弱了一点
    不管是直接bfs+hash(用vector保存)还是二进制+SPFA都是0ms秒杀?
    也是醉了
    学习了~再一次感受到了隐式图搜索的内涵
    和补丁vs漏洞差不多的叭~
    其实搜索和最短路从某种程度上来说
    本质上是一样的吧
    这里我用的是二进制+SPFA
    首先我们理清楚二进制的问题
    因为我们发现病情不过就是10种对吧
    那么我们如果用一个vector来保存肯定是会更麻烦并且更慢的对叭~
    那么我们可以直接二进制位运算一搞
    一个状态s其每个有效位上的0或者1必然就是表示与其对应的疾病的有无
    比如最低位为1表示第一种病是有的
    那么我们可以用两个数组a[],b[]分别记录下药性
    a[i]的二进制位上为1表示i这种药可以治愈对应的病
    同理b[i]的二进制位上为1表示i这种药可以导致得对应的病
    那么我们可以先预处理出a[] b[]
    然后我们就以所有病都有的状态s为源点开始SPFA    有s=(1<<n)-1
    关键是如何建立隐式图?
    即如何从一个结点状态扩展到另一个状态?
    这就涉及到我们的update操作了
    很奇妙的位运算
    具体也有注释了
    最后说说心得叭~
    其实感觉所有的bfs都可以转换为最短路来做
    只不过是d[i]有的时候i无法表示一个状态
    所以不太好做
    而位运算就是一种强大的工具将两者连接了起来
    算法真是奇妙>3<
    QAQ
    */
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    #include <queue>
    using namespace std;
    
    const int MAXN=12;
    const int MAXM=105;
    const int MAX=(1<<10)+5;
    const int INF=(1<<30)-1;
    queue<int> q;
    bool in[MAX];   int d[MAX];//SPFA相关
    int a[MAXM];//记录治愈药性
    int b[MAXM];//记录毒性
    int n,m;
    int s;//初始状态
    
    void init()
    {
        int x;
        cin>>n>>m;
        for(int i=1;i<=m;i++)
            for(int j=0;j<n;j++)
            {
                cin>>x;
                if(x==1)
                    a[i]|=(1<<j);
                else    if(x==-1)
                    b[i]|=(1<<j);
            }
        s=(1<<n)-1; //初始时所有患病
        for(int i=0;i<=(1<<n)-1;i++)
            d[i]=INF;
    }
    
    inline int update(int x,int k)
    {
        x&=(~a[k]);//a[k]取反之后不能治愈的变为了1,只有两个都为1才会患病
        x|=b[k];//有一个为1则这种病会患上
        return x;
    }
    
    void SPFA()
    {
        d[s]=0; q.push(s);  in[s]=1;
        while(!q.empty())
        {
            int u=q.front();    in[u]=0;    q.pop();
            for(int i=1;i<=m;i++)
            {
                int v=update(u,i);
                if(d[v]>d[u]+1)
                {
                    d[v]=d[u]+1;
                    if(!in[v])
                        q.push(v),in[v]=1;
                }
            }
        }
        if(d[0]==INF)
            cout<<"The patient will be dead."<<endl;
        else
            cout<<d[0]<<endl;
    }
    
    int main()
    {
        init();
        SPFA();
        return 0;
    }
         
    
  • 0
    @ 2018-02-26 19:52:04

    我是一只蒟蒻,说的不对欢迎大佬指正。
    似乎没有人提出,治病的时候不会用两次同一种药。
    证明:
    1.连着用两次同种药是赤裸裸的浪费。
    2.先用一次药,治好了某些病,过了一段时间又用了一次药。那么第一次的治疗是无效的,一段时间后再用药不会比原来差。

    #include<bits/stdc++.h>
    using namespace std;
    int ans=1e9;
    int n,m,a[110][110],q[(1<<12)+10];
    bool v[110];
    void search(int s,int f)//标准剪枝dfs
    {
    if(s==0){
    if(f<ans) ans=f;
    return;
    }
    if(f>=ans) return;
    if(q[s]<=f) return;
    else q[s]=f; 
    int p=s;
    for(int t=0;t<m;t++) if(v[t]){//v[t]记录是否用过这种药,用过则不用第二次
    v[t]=false;
    for(int i=0;i<n;i++){
    if(a[t][i]==-1) s|=(1<<i);
    if(a[t][i]==1 && s&(1<<i))
    s^=(1<<i); 
    }
    if(s==0){
    v[t]=true;
    if(f+1<ans) ans=f+1;
    return;
    }
    search(s,f+1);
    v[t]=true;
    s=p;
    }
    return;
    }
    int main()
    {
    scanf("%d",&n);
    scanf("%d",&m);
    for(int i=0;i<m;i++){
    for(int j=0;j<n;j++){
    scanf("%d",&a[i][j]);
    }
    }
    memset(v,true,sizeof(v));
    memset(q,127,sizeof(q));
    search((1<<(n))-1,0);
    if(ans>0&&ans<1e6)
    printf("%d\n",ans);
    else printf("The patient will be dead.\n");
    return 0;
    }
    
  • 0
    @ 2018-02-26 19:41:43

    我是一只蒟蒻,说的不对欢迎大佬指正。

    似乎没有人提出,治病的时候不会用两次同一种药。

    证明:
    1.连着用两次同种药是赤裸裸的浪费。
    2.先用一次药,治好了某些病,过了一段时间又用了一次药。那么第一次的治疗是无效的,一段时间后再用药与先用一次药状态一样。

    #include<bits/stdc++.h>
    using namespace std;
    int ans=1e9;
    int n,m,a[110][110],q[(1<<12)+10];
    bool v[110];
    void search(int s,int f)//标准的剪枝dfs,具体参见下方某题解
    {
        if(s==0){
            if(f<ans) ans=f;
            return;
        }
        if(f>=ans) return;
        if(q[s]<=f) return;
        else q[s]=f; 
        int p=s;
        for(int t=0;t<m;t++) if(v[t]){//v[t]记录治病过程中此药是否用过
            v[t]=false;
            for(int i=0;i<n;i++){
                if(a[t][i]==-1) s|=(1<<i);
                if(a[t][i]==1 && s&(1<<i))
                    s^=(1<<i); 
            }
            if(s==0){
                v[t]=true;
                if(f+1<ans) ans=f+1;
                return;
            }
            search(s,f+1);
            v[t]=true;
            s=p;
        }
        return;
    }
    int main()
    {
        scanf("%d",&n);
        scanf("%d",&m);
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                scanf("%d",&a[i][j]);
            }
        }
        memset(v,true,sizeof(v));
        memset(q,127,sizeof(q));
        search((1<<(n))-1,0);
        if(ans>0&&ans<1e6)
            printf("%d\n",ans);
        else printf("The patient will be dead.\n");
        return 0;
    }
    
  • 0
    @ 2017-06-11 12:23:40

    1019的弱化版。。。
    此题由于n<=10,而2^10=1024因此可以使用状态压缩
    那么可以想到一个简单的搜索,每一次用一种药。
    这样的搜索加上hash判重以及最优性剪枝速度是比较快的。

    #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;
    }
    int n,m,ans=0x7fffffff/2,Effect[105][25],Hash[2505];
    void Dfs(int state,int ttime) {
        if(ttime>ans)return;
        if(Hash[state]<=ttime)return;
        Hash[state]=ttime;
        if(state==0) {
            ans=min(ans,ttime);
            return;
        }
        int nextstate;
        for(int i=1; i<=m; i++) {
            nextstate=state;
            for(int j=1; j<=n; j++)
                if((state&(1<<(j-1)))&&Effect[i][j]==-1)nextstate^=1<<(j-1);
                else if(!(state&(1<<(j-1)))&&Effect[i][j]==1)nextstate^=1<<(j-1);
            Dfs(nextstate,ttime+1);
        }
    }
    int main() {
        n=Get_Int();
        m=Get_Int();
        for(int i=1; i<=m; i++)
            for(int j=1; j<=n; j++)
                Effect[i][j]=-Get_Int();
        memset(Hash,0x3f,sizeof(Hash));
        Dfs((1<<n)-1,0);
        if(ans==0x7fffffff/2)puts("The patient will be dead.");
        else printf("%d\n",ans);
        return 0;
    }
    
    

    仔细思考,这样的搜索本质其实与最短路没有区别。
    将状态看作点,状态转移看作边,时间(1)是边权。
    那么我们的hash判重其实就是spfa的inque数组,因此可以跑一遍最短路。

    #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;
    }
    struct Edge {
        int from,to,dist;
    };
    vector<Edge>edges[2505];
    int dist[2505],inque[2505],n,m,Effect[105][25];
    void AddEdge(int x,int y,int v) {
        edges[x].push_back((Edge) {
            x,y,v
        });
    }
    void Spfa(int s) {
        memset(dist,0x3f,sizeof(dist));
        queue<int>Q;
        Q.push(s);
        inque[s]=1;
        dist[s]=0;
        while(!Q.empty()) {
            int Now=Q.front();
            inque[Now]=0;
            Q.pop();
            for(int i=0; i<edges[Now].size(); i++) {
                Edge& e=edges[Now][i];
                int Next=e.to;
                if(dist[Now]+e.dist<dist[Next]) {
                    dist[Next]=dist[Now]+e.dist;
                    if(!inque[Next]) {
                        inque[Next]=1;
                        Q.push(Next);
                    }
                }
            }
        }
    }
    int Get_Next(int state,int num) {
        int nextstate=state;
        for(int j=1; j<=n; j++)
            if((state&(1<<(j-1)))&&Effect[num][j]==-1)nextstate^=1<<(j-1);
            else if(!(state&(1<<(j-1)))&&Effect[num][j]==1)nextstate^=1<<(j-1);
        return nextstate;
    } 
    int main() {
        n=Get_Int();
        m=Get_Int();
        for(int i=1; i<=m; i++)
            for(int j=1; j<=n; j++)
                Effect[i][j]=-Get_Int();
        for(int i=0; i<=(1<<n)-1; i++)
            for(int j=1; j<=m; j++)
                AddEdge(i,Get_Next(i,j),1);
        Spfa((1<<n)-1);
        if(dist[0]==0x3f3f3f3f)puts("The patient will be dead.");
        else printf("%d\n",dist[0]);
        return 0;
    }
    
    
  • 0
    @ 2016-12-04 00:10:40

    评测结果
    编译成功
    测试数据 #0: Accepted, time = 0 ms, mem = 572 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 592 KiB, score = 10
    测试数据 #2: Accepted, time = 15 ms, mem = 576 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 624 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 576 KiB, score = 10
    测试数据 #5: Accepted, time = 0 ms, mem = 592 KiB, score = 10
    测试数据 #6: Accepted, time = 0 ms, mem = 592 KiB, score = 10
    测试数据 #7: Accepted, time = 15 ms, mem = 636 KiB, score = 10
    测试数据 #8: Accepted, time = 15 ms, mem = 576 KiB, score = 10
    测试数据 #9: Accepted, time = 0 ms, mem = 580 KiB, score = 10
    Accepted, time = 45 ms, mem = 636 KiB, score = 100

    总觉得有情况没考虑到但还是AC了。。。
    记忆化BFS

    代码
    c++
    #include<iostream>
    #include<iomanip>
    #include<cstring>
    #include<vector>
    #include<sstream>
    #include<algorithm>
    #include<string>
    #include<cstdio>
    #include<math.h>
    #include<map>
    #include<cctype>
    #include<queue>
    #include<functional>
    #define maxn 350
    #define INF 66666666
    #define min(a,b) (a)>(b)?(b):(a)
    #define Mem(a,b) memset((a),(b),sizeof((a)))
    using namespace std;
    struct Node
    {
    vector<int> diss; int step;
    Node(vector<int> a, int b) :diss(a), step(b) {}
    Node(){}
    friend bool operator < (Node a, Node b)
    {
    return a.step > b.step;
    }
    };
    map<vector<int>, int> mem;
    int n, m;
    int drug[110][20];
    bool judge(const vector<int>& a){
    for (int i = 1; i <= n; i += 1)
    if (a[i] != 0)
    return false;
    return true;
    }
    int main(){
    cin >> n >> m;
    for (int i = 1; i <= m; i += 1)
    for (int j = 1; j <= n; j += 1)
    cin >> drug[i][j];
    priority_queue<Node> Q;
    Node s(vector<int> (n+1,-1), 0),now;
    Q.push(s);
    while (!Q.empty()){
    now = Q.top(); Q.pop();
    for (int i = 1; i <= m; i += 1){
    s = now;
    for (int j = 1; j <= n; j += 1){
    s.diss[j] += drug[i][j];
    if (s.diss[j] >= 1)
    s.diss[j] = 0;
    if (s.diss[j] < -1)
    s.diss[j] = -1;
    }
    if (mem.count(s.diss)==0)
    {
    if (!judge(s.diss))
    {
    s.step += 1;
    mem[s.diss] = 1;
    Q.push(s);
    }
    else
    {
    cout << s.step + 1 << endl;
    return 0;
    }
    }
    }
    }
    cout << "The patient will be dead." << endl;
    return 0;
    }

  • 0
    @ 2016-11-01 23:16:17

    #include <cstdio>
    #include <queue>
    #define add(a,k) a|=(1<<k)
    #define INF 999999999

    int n,m;
    int b1[150]={0},b2[150]={0};

    std::queue<int> q;
    int dist[1111];
    int inque[1111]={0};

    void spfa(int u){
    for(int i=0;i<1111;i++)
    dist[i]=INF;
    dist[u]=0;
    q.push(u),inque[u]=1;
    while(!q.empty()){
    int t=q.front();
    q.pop(),inque[t]=0;
    for(int i=1;i<=m;i++){
    int p=t;
    p&=(~b1[i]),p|=b2[i];
    if(dist[p]>dist[t]+1){
    dist[p]=dist[t]+1;
    if(!inque[p]){
    q.push(p);
    inque[p]=1;
    }
    }
    }
    }
    }

    int main(){
    freopen("in.txt","r",stdin);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
    int k;
    for(int j=0;j<n;j++){
    scanf("%d",&k);
    if(k==1)
    add(b1[i],j);
    if(k==-1)
    add(b2[i],j);
    }
    }
    int start=(1<<n)-1;
    spfa(start);
    if(dist[0]==INF)
    printf("The patient will be dead.");
    else
    printf("%d",dist[0]);
    return 0;
    }

  • 0
    @ 2016-10-02 15:43:29

    // 广度搜索+hash
    #include <iostream>
    #include <cstring>
    #include <queue>

    using namespace std;

    int n;//n疾病个数
    int m;//m药剂个数
    int ill[101][11];//药剂详情
    vector <int> peo;//患者
    queue <int> que;//队列
    queue < vector <int> > qra;//治疗情况
    queue <int> ans;//药剂个数
    vector <int> ptt;//患者临时表

    bool a[2000];//哈希表

    bool kot = true;

    inline bool dpra()
    {
    for (int i = 1; i <= n; ++i)
    if (qra.back()[i] == -1)return false;//判断是否有效,无效返回false
    return true;
    }

    inline bool hashx()//哈希表,如果病症出现过,就不需要入队了
    {
    int i;
    long long x = 1, sd = 0;
    for (i = 1; i <= n; ++i)
    {
    sd += ptt[i] * x+100;
    x *= 2;
    }
    if (a[sd])return true;
    a[sd] = true;
    return false;
    }

    int bfs()
    {
    int head = 0, tail = 1;
    que.push(0);
    ans.push(0);
    qra.push(peo);
    int i, j;
    do
    {
    for (i = 1; i <= m; ++i)
    {
    ptt.resize(0);
    if (que.front() == i)continue;
    ptt.push_back(-1);
    for (j = 1; j <= n; ++j)
    {
    switch (ill[i][j])
    {
    case 1:
    ptt.push_back(0);
    break;
    case -1:
    ptt.push_back(-1);
    break;
    default://case 0:
    ptt.push_back(qra.front()[j]);
    break;
    }
    }
    if (hashx())continue;
    que.push(i);
    ans.push(ans.front() + 1);
    qra.push(ptt);
    if (dpra()) { cout << ans.back(); kot = false; return 0; }
    ++tail;
    }
    ++head;
    que.pop();
    qra.pop();
    ans.pop();
    } while (head < tail);
    return 0;
    }

    int main()
    {
    int i, j;
    cin >> n >> m;//n疾病个数,m药剂个数
    for (i = 0; i <= n; ++i)
    peo.push_back(-1);
    for (i = 1; i <= m; ++i)
    for (j = 1; j <= n; ++j)
    cin >> ill[i][j];
    bfs();
    if (kot)cout << "The patient will be dead.";
    system("pause");
    return 0;
    }

    • @ 2016-12-03 19:47:50

      感谢dalao的思路

  • 0
    @ 2016-10-02 15:42:17

    测试数据 #0: Accepted, time = 0 ms, mem = 584 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 592 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 588 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 592 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 588 KiB, score = 10
    测试数据 #5: Accepted, time = 0 ms, mem = 588 KiB, score = 10
    测试数据 #6: Accepted, time = 0 ms, mem = 588 KiB, score = 10
    测试数据 #7: Accepted, time = 0 ms, mem = 584 KiB, score = 10
    测试数据 #8: Accepted, time = 0 ms, mem = 588 KiB, score = 10
    测试数据 #9: Accepted, time = 0 ms, mem = 588 KiB, score = 10
    Accepted, time = 0 ms, mem = 592 KiB, score = 100

  • 0
    @ 2016-09-17 22:18:11

    发一个广搜+hash+二进制的代码

    c++
    #include<iostream>
    #include<cstdio>
    using namespace std;
    int n,m,ans=150;
    int tre[110][15];
    int hash_[1050]={0};
    int st[15],d[1050][15]={0};
    int finish;
    int Hash_(int a[]){
    int i,x=1,s=0;
    for(i=1;i<=n;i++){
    s+=a[i]*x;
    x*=2;
    }
    return s;
    }
    void bfs(){
    int i,j,head=1,tail=2;
    hash_[0]=1;
    finish=(1<<n)-1;//末态
    while(head<tail){
    for(i=1;i<=m;i++){
    for(j=1;j<=n;j++){
    if(tre[i][j]==1) st[j]=1;
    else if(tre[i][j]==-1) st[j]=0;
    else st[j]=d[head][j];//如果无影响,则该病的状态为上次的状态
    }
    int x=Hash_(st);
    if(!hash_[x]){
    hash_[x]=1;
    for(j=1;j<=n;j++){
    d[tail][j]=st[j];//记录下当前的每种病的状态;
    }
    d[tail][0]=d[head][0]+1;//加入队列中的状态由当前状态得到
    tail++;
    }
    if(hash_[finish]){//如果当前已完成末态,则输出
    cout<<d[tail-1][0];//注意是tail-1;因为tail++;
    return;
    }
    }
    head++;
    }
    cout<<"The patient will be dead.";
    }
    int main(){
    freopen("in.txt","r",stdin);
    int i,j;
    scanf("%d %d",&n,&m);
    for(i=1;i<=m;i++){
    for(j=1;j<=n;j++){
    scanf("%d",&tre[i][j]);
    }
    }
    bfs();
    return 0;
    }

  • 0
    @ 2016-08-19 16:43:44

    位运算+SPFA 和 补丁vs错误很像
    #include <cstdio>
    #include <cstring>
    #include <queue>
    #define add(A,K) A|=1<<K

    int n,m,st;
    int A[110]={0},B[110]={0};

    int update(int x,int way){
    x&=(~A[way]);
    x|=B[way];
    return x;
    }

    std::queue<int> q;
    int inque[1<<10+10]={0};
    int dist[1<<10+10];

    void spfa(){
    dist[st]=0,q.push(st),inque[st]=1;
    while(!q.empty()){
    int t=q.front();
    q.pop(),inque[t]=0;
    for(int i=1;i<=m;i++){
    int v=update(t,i);
    if(dist[t]+1<dist[v]){
    dist[v]=dist[t]+1;
    if(inque[v]==0){
    q.push(v);
    inque[v]=1;
    }
    }
    }
    }
    }

    int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    for(int j=0;j<n;j++){
    int q;
    scanf("%d",&q);
    if(q==1)
    add(A[i],j);
    else if(q==-1)
    add(B[i],j);
    }
    st=(1<<n)-1;
    for(int i=0;i<=1<<10+5;i++)
    dist[i]=99999999;
    spfa();
    if(dist[0]==99999999)
    printf("Don't copy my code or you will get a WA!");
    else
    printf("%d",dist[0]);

    return 0;
    }

  • 0
    @ 2016-01-24 12:57:20

    好吧。。。。我承认自己的代码比较蠢。。。但是对初学者还是可能有用的吧。。请求各位大神不要嘲笑我。。
    #include<iostream>
    #include<cmath>
    using namespace std;
    struct qu { bool sta[17];} ;
    int n, m;//疾病种数,药剂数
    int in[107][17];
    qu now[2000000];
    bool used[1030] = {0};
    bool check(qu l)
    {
    for(int i = 1; i <= n; i++)
    if(l.sta[i] == 0)
    return 0;
    return 1;
    }
    bool j(bool a, int b)//0代表有病,1代表没病
    {
    if(a == 1 && b == 1)
    return 1;
    if(a == 0 && b == -1)
    return 0;
    return a + b;
    }
    qu jia(int mm, qu l)
    {
    for(int i = 1; i <= n; i++)
    l.sta[i] = j(l.sta[i], in[mm][i]);
    return l;
    }
    int cnt = 0;
    int find(qu l)
    {
    int k = 0;
    for(int i = 1; i <= n; i++)
    if(l.sta[i])
    k += (int)pow(2, i - 1);
    return k;
    }
    void bfs()
    {
    int head = 0, tail = 0;
    for(int i = 1; i <= n; i++)
    {
    now[tail].sta[i] = 0;
    }
    while(head <= tail)
    {
    int cur = tail, x = 0;
    for( ; head <= cur; head++)
    {
    for(int i = 1; i <= m; i++)
    {
    qu l = now[head];
    l = jia(i, l);
    int j = find(l);
    if(check(l))
    {
    x = 1;
    used[j] = 1;
    }
    else if(!used[j])
    {
    tail++;
    used[j] = 1;
    now[tail] = l;
    }
    }
    }
    cnt++;
    if(x == 1)
    break;
    }
    }
    int main()
    {
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
    for(int j = 1; j <= n; j++)
    cin >> in[i][j];
    bfs();
    if(used[(int)pow(2, n) - 1])
    cout << cnt;
    else cout << "The patient will be dead.";
    return 0;
    }

  • 0
    @ 2015-11-03 08:39:15

    最简单的BFS 用一个int来记录当前情况每一位表示有没有患病
    #include <cstdio>
    #include <algorithm>
    #include <queue>
    using namespace std;
    struct state{
    int x,dis;
    state(int x,int dis):x(x),dis(dis){}
    };
    queue<state> q;
    int n,m,med[110][20],vis[2000],l,r;

    int main(){
    freopen("1026.in","r",stdin);freopen("1026.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    for(int j=1;j<=n;j++) scanf("%d",&med[i][j]);
    int s=~0u>>(32-n);
    q.push(state(s,0));vis[s]=true;
    while(!q.empty()){
    state t=q.front();q.pop();
    for(int i=1;i<=m;i++){
    int tmp=t.x;
    for(int j=1;j<=n;j++)
    if(med[i][j]== 1) tmp&=~(1<<(j-1));
    else if(med[i][j]==-1) tmp|=(1<<(j-1));
    if(tmp==0) {printf("%d",t.dis+1); return 0;}
    else if(!vis[tmp]) q.push(state(tmp,t.dis+1)),vis[tmp]=true;
    }
    }
    printf("The patient will be dead.");
    return 0;
    }

  • 0
    @ 2015-10-31 11:10:55

    状态压缩的BFS,类似 P1019 和 P1197
    数据范围很小,可以秒杀,估计把疾病数上升到20,药品数上升到200也是可以的

    //vijos p1206
    #include <stdio.h>
    #define STATUS 0
    #define STEP 1

    int table[120][10];
    short searched[1<<15];
    int queue[1<<15][2];
    int head, tail;

    void addToQueue(int status, int step){
    if(!searched[status]){
    searched[status] = 1;
    queue[tail][STATUS] = status;
    queue[tail][STEP] = step;
    tail++;
    }
    }
    int bfs(int numIllness, int numDrug){
    int status, step, i, j, tmp, target;
    head = tail = 0;
    target = (1<<numIllness) - 1; //all illnesses have been cured
    addToQueue(0, 0); //all illnesses haven't been cured
    while(head < tail){
    status = queue[head][STATUS];
    step = queue[head][STEP];
    if(status == target)
    return step;
    for(i=0; i<numDrug; i++){
    tmp = status;
    for(j=0; j<numIllness; j++){
    switch(table[i][j]){
    case 1:
    tmp |= (1<<j);
    break;
    case -1:
    tmp &= (target^(1<<j));
    }
    }
    addToQueue(tmp, step+1);
    }
    head++;
    }
    return -1;
    }
    int main(){
    int numIllness, numDrug;
    int i, j;

    scanf("%d %d", &numIllness, &numDrug);
    for(i=0; i<numDrug; i++){
    for(j=0; j<numIllness; j++)
    scanf("%d", &table[i][j]);
    }
    for(i=0; i<(1<<numIllness); i++)
    searched[i] = 0;

    i = bfs(numIllness, numDrug);
    if(i < 0)
    printf("The patient will be dead.\n");
    else
    printf("%d\n", i);

    return 0;
    }

  • 0
    @ 2015-01-24 18:32:53

    把每个"得病状态"(得了哪些病,没得哪些病)当做节点.
    总结点数不会超过2^n个.
    如果状态i能通过吃一种药到达状态j,就连一条i到j的有向边
    跑无权最短路就好了......
    用位运算广搜秒掉了....
    不用位运算的常数应该也可以承受....

  • 0
    @ 2014-11-03 16:41:03

    原来大神们都是用位运算的啊……我是渣渣,这里写一个非位运算的宽搜:倒着往前搜……
    还是看代码吧,我加了注释,应该很好理解。

    //Vijos 1026
    #include<queue>
    #include<vector>
    #include<cstdio>
    #include<cstring>
    #include<cstdlib>
    #include<iostream>
    #include<algorithm>
    #define rep(i,n) for(int i=0;i<n;++i)
    #define r(i,j,n) for(int i=j;i<=n;++i)
    #define pb push_back
    using namespace std;
    const int N=101;
    //倒着搜:因为现在治不好的以后不知道什么时候可能能治好
    //而倒着搜的话,只有现在能治好的病,过去才可以得
    int n,m,a[N][11],b[220][11],Q[220],num[220];

    void out(int x)
    {
    printf("this is %d\n",x);
    r(i,1,n)
    printf("%d ",b[x][i]);
    cout <<endl;
    }//debug

    int main()
    {
    freopen("file.in","r",stdin);
    // freopen("file.out","w",stdout);
    scanf("%d%d",&n,&m);
    int l=0,r=0;
    r(i,1,m){
    int sign=1;
    r(j,1,n){
    scanf("%d",&a[i][j]);
    if (a[i][j]==-1) sign=0;
    }
    if (sign) { Q[r++]=i; num[r-1]=1; r(k,1,n) b[r-1][k]=a[i][k]; }
    }

    if (!r) {printf("The patient will be dead.\n"); return 0;}

    while(l!=r){
    bool check=1;
    r(k,1,n) if (b[l][k]!=1){check=0;break;}
    if (check) {printf("%d\n",num[l]);}
    r(j,1,m){
    if (j==Q[l]) continue;//刚刚吃过的药再吃没意义……
    // out(l);
    bool sign1=1,sign2=0;
    r(k,1,n)
    if (a[j][k]==-1 && b[l][k]!=1) {sign1=0;break;}//如果过去要得的病现在治不了,则不扩展
    r(k,1,n)
    if (a[j][k]==1 && b[l][k]==0) {sign2=1;break;}//如果对当前状态无增益(不能多治任何一种病)则不扩展
    // cout <<sign1<<" "<<sign2<<endl;
    if (sign1 && sign2) {
    Q[r]=j;
    num[r]=num[l]+1;//用的药的数量加一
    r(k,1,n)
    if(a[j][k]==1) b[r][k]=1;
    else b[r][k]=b[l][k];//更新状态
    r=(r+1)%200;//循环队列,队尾指针加一
    // out(r-1);
    bool check=1;
    r(k,1,n) if (b[r-1][k]!=1){check=0;break;}
    if (check) {printf("%d\n",num[r-1]); return 0;}//判断当前是否能治愈
    }
    }
    l=(l+1)%200;//队首指针+1(循环队列)
    }
    printf("The patient will be dead.\n");
    return 0;
    }
    //90

    • @ 2014-11-03 16:42:17

      PS:那个队列的长度200是不够的,我就因为这个只得了90分……改长以后才AC的,一定要吸取教训啊!
      循环队列如果空间允许千万不要抠门!!尽量多开

  • 0
    @ 2013-10-17 09:37:08

    and 和 or 的优先级弄错了导致WA了4次- -、

    var
    n,m,way,i,zy,bzy,medicine,j,k,l,r : longint;
    dis : array[0..1027] of longint;
    q : array[0..10007] of longint;
    vis : array[0..1027] of boolean;
    map : array[0..1027,0..1027] of boolean;

    begin
    readln(n); readln(m);
    way := (1<<n)-1;
    for i := 1 to m do begin
    zy := 0; bzy := way;
    for j := 1 to n do begin
    read(medicine);
    if medicine=1 then zy := zy or (1<<(j-1)) else
    if medicine=-1 then bzy := bzy and (not (1<<(j-1)));
    end;
    for k := 0 to way do
    map[k,(k or zy) and bzy] := true;
    end;
    l := 1; r := 1; q[1] := 0; dis[0] := 0; vis[0] := true;
    while l<=r do begin
    k := q[l];
    for i := 0 to way do
    if (map[k,i])and(not vis[i]) then begin
    inc(r); q[r] := i; dis[i] := dis[k]+1; vis[i] := true;
    end;
    inc(l);
    end;
    if dis[way]=0 then writeln('The patient will be dead.') else writeln(dis[way]);
    end.

  • 0
    @ 2013-09-21 20:30:18

    去年做这道题,一直没有感觉。
    现在学了hash以后就知道了
    因为n的范围小,总共的状态不会超过2^n
    所以搜索+hash就可以
    其实判重直接在已经有的状态里找一遍有没有相同的也行。
    因为就算2^n^2也不会超

    DXE-SYF

  • 0
    @ 2013-02-16 10:13:53
  • 0
    @ 2012-10-31 16:47:41

    感谢发最短路题解的大牛们 真是个好思路!

信息

ID
1026
难度
5
分类
搜索 | 搜索与剪枝 点击显示
标签
(无)
递交数
2920
已通过
933
通过率
32%
被复制
1
上传者