蒟蒻的想法 - Vijos

毒药？解药？
Diogenes LV 4 @ 2018-02-26 19:55:05

我是一只蒟蒻，说的不对欢迎大佬指正。
似乎没有人提出，治病的时候不会用两次同一种药。
证明：
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;
}

孙鹤鸣 (sunheming) LV 10 @ 2020-03-23 13:37:44

spfa，注意毒解完了之后还可以中同样的毒…

#include<cstdio>
#include<queue>
#define INF (1<<30)-1
using namespace std;

int n,m,s;
queue<int> q;
int a[105],b[105],d[(1<<10)+5];
bool vis[(1<<10)+5];

int readln()
{
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
    while ('0'<=ch&&ch<='9') x=x*10+ch-48,ch=getchar();
    return x*f;
}

inline int update(int x,int k)
{
    x&=(~a[k]);x|=b[k];
    return x;
}

int main()
{
    n=readln();m=readln();s=(1<<n)-1;
    for (int i=1;i<=m;i++)
        for (int j=0;j<n;j++)
        {
            int x=readln();
            if (x==1) a[i]|=(1<<j); else if(x==-1) b[i]|=(1<<j);
        }
    for (int i=0;i<=(1<<n)-1;i++) d[i]=INF;
    d[s]=0;q.push(s);vis[s]=true;
    while (!q.empty())
    {
        int x=q.front();
        vis[x]=false;q.pop();
        for (int i=1;i<=m;i++)
        {
            int y=update(x,i);
            if (d[y]>d[x]+1)
            {
                d[y]=d[x]+1;
                if (!vis[y]) {q.push(y);vis[y]=true;}
            }
        }
    }
    if (d[0]==INF) printf("The patient will be dead."); else printf("%d",d[0]);
    return 0;
}

ID: 1026
难度: 6
分类: 搜索 | 搜索与剪枝点击显示
标签: (无)
递交数: 3669
已通过: 1112
通过率: 30%
被复制: 20
上传者: Vivian Snow