题解

101 条题解

  • 5
    @ 2017-05-07 12:51:28
    /*
    可以这很强势
    一遍写完调试了两分钟过了样例直接AC秒杀~
    和P1026很像    都是可以位运算处理然后转换SPFA
    当然bfs+hash也是可以的
    题目的确有点繁琐(当初看到这个逃了好几次)
    但是静下心来仔细看就好了
    check函数和get函数很精妙
    位运算又进一步加强了
    这种题目还是要自己多写写好
    详细看P1026的题解叭~~~
    */
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    #include <queue>
    using namespace std;
    
    const int MAXN=(1<<16)-1;
    const int MAXM=102;
    const int INF=(1<<30)-1;
    int B1[MAXM],B2[MAXM];
    int F1[MAXM],F2[MAXM];
    bool in[MAXN];
    queue<int> q;
    int t[MAXM];
    int d[MAXN];
    int n,m;
    int s;
    
    void init()
    {
        string a,b;
        cin>>n>>m;
        s=(1<<n)-1;
        for(int i=1;i<=m;i++)
        {
            cin>>t[i]>>a>>b;
            for(int j=0;j<n;j++)
                if(a[j]=='+')
                    B1[i]|=(1<<j);
                else    if(a[j]=='-')
                    B2[i]|=(1<<j);
            for(int j=0;j<n;j++)
                if(b[j]=='-')
                    F1[i]|=(1<<j);
                else    if(b[j]=='+')
                    F2[i]|=(1<<j);
        }
        for(int i=0;i<MAXN;i++)
            d[i]=INF;
    }
    
    bool check(int x,int k)
    {
        for(int i=0;i<n;i++)
            if((1<<i)&B1[k]&&(!((1<<i)&x)))
                return 0;
        for(int i=0;i<n;i++)
            if((1<<i)&B2[k]&&(1<<i)&x)
                return 0;
        return 1;
    }
    
    int get(int x,int k)
    {
        x&=(~F1[k]);
        x|=F2[k];
        return x;
    }
    
    void SPFA()
    {
        d[s]=0; q.push(s);  in[s]=1;
        while(!q.empty())
        {
            int u=q.front();    q.pop();
            in[u]=0;
            for(int i=1;i<=m;i++)
            {
                if(!check(u,i))
                    continue;
                int v=get(u,i);
                if(d[v]>d[u]+t[i])
                {
                    d[v]=d[u]+t[i];
                    if(!in[v])
                    {
                        q.push(v);
                        in[v]=1;
                    }
                }
            }
        }
        if(d[0]==INF)
            cout<<0<<endl;
        else
            cout<<d[0]<<endl;
    }
    
    int main()
    {
        init();
        SPFA();
        return 0;
    }
         
    
    • @ 2020-07-08 21:27:40

      关于SPFA,TA死了……

  • 2
    @ 2017-05-08 17:56:32

    貌似就我一个人傻傻的用dfs。贴一下吧,虽然速度不咋地- -
    //位运算+dfs

    #include<iostream>
    #include<math.h>
    #include<string>
    #include<memory.h>
    using namespace std;
    const int MAXN = 15;
    const int MAXM = 101;
    const int MAXV = 32768;
    const int MAXT = 10000000;
    
    typedef pair<int, int> P ;
    
    struct Node {
        int time;
        P con[MAXN];
        int clen;
        P tra[MAXN];
        int tlen;
    }nodes[MAXM];
    bool vis[MAXV];
    int n, m;
    int tans = 0;
    int ans = MAXT;
    
    bool OK(int sta, Node node) {
        int k;
        for (int i = 0; i<node.clen; i++) {
            k = node.con[i].first;
            if ((1 & (sta >> k)) != node.con[i].second)
                return 0;
        }
        return 1;
    }
    
    int nextSta(int sta, Node node) {
        int k;
        for (int i = 0; i<node.tlen; i++) {
            k = node.tra[i].first;
            sta = sta - ((1 << k)&sta) + (node.tra[i].second << k);
        }
        return sta;
    }
    
    void dfs(int sta) {
        vis[sta] = 1;
        if (tans >= ans);
        else if (sta == 0) {
            if (tans<ans)
                ans = tans;
        }
        else {
            int nextsta;
            for (int i = 0; i<m; i++) {
                if (OK(sta, nodes[i])) {
                    nextsta = nextSta(sta, nodes[i]);
                    if (!vis[nextsta]) {
                        tans += nodes[i].time;
                        dfs(nextsta);
                        tans -= nodes[i].time;
                    }
                }
            }
        }
        vis[sta] = 0;
    }
    
    int main() {
        cin >> n >> m;
        string str1, str2;
        int i, j;
        for (i = 0; i<m; i++) {
            cin >> nodes[i].time >> str1 >> str2;
            nodes[i].clen = 0;
            nodes[i].tlen = 0;
            for (j = 0; j<n; j++) {
                switch (str1[j]) {
                case '0':
                    break;
                case '+':
                    nodes[i].con[nodes[i].clen].first = j;
                    nodes[i].con[nodes[i].clen].second = 1;
                    nodes[i].clen++;
                    break;
                case '-':
                    nodes[i].con[nodes[i].clen].first = j;
                    nodes[i].con[nodes[i].clen].second = 0;
                    nodes[i].clen++;
                    break;
                }
                switch (str2[j]) {
                case '0':
                    break;
                case '+':
                    nodes[i].tra[nodes[i].tlen].first = j;
                    nodes[i].tra[nodes[i].tlen].second = 1;
                    nodes[i].tlen++;
                    break;
                case '-':
                    nodes[i].tra[nodes[i].tlen].first = j;
                    nodes[i].tra[nodes[i].tlen].second = 0;
                    nodes[i].tlen++;
                    break;
                }
            }
        }
        memset(vis, 0, sizeof(vis));
        dfs((1 << n) - 1);
        if (ans != MAXT)
            cout << ans << endl;
        else
            cout << 0 << endl;
        return 0;
    }
    
  • 2
    @ 2017-04-18 22:14:56

    状态

    耗时

    内存占用

    #1  Accepted  4ms 2.469MiB
    #2  Accepted  3ms 2.5MiB
    #3  Accepted  3ms 2.375MiB
    #4  Accepted  3ms 2.5MiB
    #5  Accepted  4ms 2.375MiB
    #6  Accepted  3ms 2.375MiB
    #7  Accepted  3ms 2.379MiB
    #8  Accepted  4ms 2.375MiB
    #9  Accepted  6ms 6.367MiB
    #10  Accepted  4ms 2.5MiB

  • 1
  • 1
    @ 2017-06-11 11:37:54

    此题由于n<=15,而2^15<35000因此可以使用状态压缩
    那么可以想到一个简单的搜索,每一次判断可以用的补丁就补上。
    这样的搜索加上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,Time[105],Use[105][25],Effect[105][25],Hash[70005];
    bool Check(int state,int num) {
        for(int i=1; i<=n; i++) {
            if(!(state&(1<<(i-1)))&&Use[num][i]==1)return false;
            if((state&(1<<(i-1)))&&Use[num][i]==-1)return false;
        }
        return true;
    }
    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++) {
            if(!Check(state,i))continue;
            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+Time[i]);
        }
    }
    int main() {
        ios::sync_with_stdio(false);
        cin>>n>>m;
        for(int i=1; i<=m; i++) {
            cin>>Time[i];
            for(int j=1; j<=n; j++) {
                char x;
                cin>>x;
                if(x=='-')Use[i][j]=-1;
                if(x=='+')Use[i][j]=1;
            }
            for(int j=1; j<=n; j++) {
                char x;
                cin>>x;
                if(x=='-')Effect[i][j]=-1;
                if(x=='+')Effect[i][j]=1;
            }
        } 
        memset(Hash,0x3f,sizeof(Hash));
        Dfs((1<<n)-1,0);
        if(ans==0x7fffffff/2)puts("0");
        else printf("%d\n",ans);
        return 0;
    }
    
    

    仔细思考,这样的搜索本质其实与最短路没有区别。
    将状态看作点,状态转移看作边,时间是边权。
    那么我们的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[35005];
    int dist[35005],inque[35005],n,m,Time[105],Use[105][25],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);
                    }
                }
            }
        }
    }
    bool Check(int state,int num) {
        for(int i=1; i<=n; i++) {
            if(!(state&(1<<(i-1)))&&Use[num][i]==1)return false;
            if((state&(1<<(i-1)))&&Use[num][i]==-1)return false;
        }
        return true;
    }
    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() {
        ios::sync_with_stdio(false);
        cin>>n>>m;
        for(int i=1; i<=m; i++) {
            cin>>Time[i];
            for(int j=1; j<=n; j++) {
                char x;
                cin>>x;
                if(x=='-')Use[i][j]=-1;
                if(x=='+')Use[i][j]=1;
            }
            for(int j=1; j<=n; j++) {
                char x;
                cin>>x;
                if(x=='-')Effect[i][j]=-1;
                if(x=='+')Effect[i][j]=1;
            }
        } 
        for(int i=0; i<=(1<<n)-1; i++)
            for(int j=1; j<=m; j++)
                if(Check(i,j))AddEdge(i,Get_Next(i,j),Time[j]);
        Spfa((1<<n)-1);
        if(dist[0]==0x3f3f3f3f)puts("0");
        else printf("%d\n",dist[0]);
        return 0;
    }
    
    
  • 1
    @ 2017-04-18 22:15:05

    状态

    耗时

    内存占用

    #1  Accepted  4ms 2.469MiB
    #2  Accepted  3ms 2.5MiB
    #3  Accepted  3ms 2.375MiB
    #4  Accepted  3ms 2.5MiB
    #5  Accepted  4ms 2.375MiB
    #6  Accepted  3ms 2.375MiB
    #7  Accepted  3ms 2.379MiB
    #8  Accepted  4ms 2.375MiB
    #9  Accepted  6ms 6.367MiB
    #10  Accepted  4ms 2.5MiB

  • 0
    @ 2016-08-19 16:12:54

    位运算+SPFA,每个状态为一个点
    #include <cstdio>
    #include <cstring>
    #include <queue>
    #define add(A,K) A|=1<<K

    int st,end,time[200];
    int n,m;
    int B[200]={0},B_[200]={0};
    int F[200]={0},F_[200]={0};

    void build(){
    scanf("%d%d",&n,&m);
    st=(1<<n)-1;
    end=0;
    char s1[100],s2[100];
    for(int i=1;i<=m;i++){
    scanf("%d",&time[i]);
    scanf("%s%s",s1,s2);
    for(int x=0;x<strlen(s1);x++){
    if(s1[x]=='+')
    add(B[i],x);
    if(s1[x]=='-')
    add(B_[i],x);
    }
    for(int x=0;x<strlen(s2);x++){
    if(s2[x]=='+')
    add(F[i],x);
    if(s2[x]=='-')
    add(F_[i],x);
    }
    }
    }

    int isok(int x,int way){
    int flag=1;
    flag*=(B[way]&x)==B[way];
    flag*=(B_[way]&x)==0;
    return flag;
    }

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

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

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

    }

    }

    int main(){
    for(int i=0;i<=(1<<15)+5;i++)
    dist[i]=999999999;
    build();
    spfa();
    if(dist[end]==999999999)
    printf("0");
    else
    printf("%d",dist[end]);

    return 0;
    }

  • 0
    @ 2016-07-18 14:42:56
    #include<iostream>
    #include<cstdio>
    #include<string>
    #include<vector>
    #include<queue>
    using namespace std;
    
    const int INF = 1000000000;
    const int maxn = 15;
    const int maxm = 100 + 10;
    int n, m;
    int  d[1<<maxn];
    bool done[1<<maxn];
    
    struct Patch {
        string s1, s2;
        int cost;
        Patch(string s1, string s2, int cost) : s1(s1), s2(s2), cost(cost) {}
    };
    
    vector<Patch> patchs;
    
    struct HeapNode {
        int u, d;
        HeapNode (int u, int d) : u(u), d(d) {}
        bool operator < (const HeapNode& rhs) const {
            return d > rhs.d;
        }
    };
    
    bool check (int x, const string& s) {
        for (int i = 0; i < s.length(); i++) {
            if (s[i] == '+' && !(x & (1<<i))) return false;
            if (s[i] == '-' && (x & (1<<i))) return false;
        }
        return true;
    }
    
    int add_patch (int x, const string& s) {
        for (int i = 0; i < s.length(); i++) {
            if (s[i] == '+') x |= (1<<i);
            if (s[i] == '-' && (x & (1<<i))) x ^= (1<<i);
        }
        return x;
    }
    
    void djs (void) {
        priority_queue<HeapNode> Q;
        Q.push(HeapNode((1<<n)-1, 0));
        d[(1<<n)-1] = 0;
        
        while (!Q.empty()) {
            HeapNode x = Q.top(); Q.pop();
            int u = x.u;
            if (done[u]) continue;
            done[u] = true;
            
            for (int i = 0; i < patchs.size(); i++) 
                if (check(u, patchs[i].s1)) { 
                    int to = add_patch(u, patchs[i].s2);
                    if (d[u] + patchs[i].cost < d[to]) {
                        d[to] = d[u] + patchs[i].cost;
                        Q.push(HeapNode(to, d[to]));
                    }
                }
        }
    }
    
    int main ()
    {
    //  freopen ("in.txt", "r", stdin);
        cin >> n >> m;
        int c;
        string s1, s2;
        for (int i = 0; i < m; i++) {
            cin >> c >> s1 >> s2;
            patchs.push_back(Patch(s1, s2, c));
        }
        
        for (int i = 0; i < (1<<n); i++) d[i] = INF;
        djs();
        if (d[0] >= INF) cout << 0 << "\n";
        else cout << d[0] << "\n";
        
        return 0;
    }
    
  • 0
    @ 2016-05-18 16:07:40

    数据真弱……

    #include<cstdio>
    #include<queue>
    #include<cstring>
    #include<vector>
    using namespace std;
    
    const int INF = 2147483647;
    
    struct Po
    {
        int th,dis;
        Po(int a,int b) : th(a) , dis(b) {};
        bool operator> (Po const &a) const{return dis > a.dis; }
    };
    
    struct Ed
    {
        int span;
        vector<char> nodetail;
        vector<char> fudetail;
        Ed(int a) : span(a) {};
    };
    
    int n,m;
    bool vis[32800];
    vector<Ed> edges;
    vector<Po> points;
    priority_queue<Po,vector<Po>,greater<Po> > Q;
    
    bool is_ok(int now,int th,int &next)
    {
        Ed &ed=edges[th];
        for(int i=0;i<n;i++)
        {
            if(ed.nodetail[i]=='+'&& (  ( now&(1<<(n-1-i)) )!=(1<<(n-1-i)) ) ) return false;
            if(ed.nodetail[i]=='-'&&  ((now&(1<<(n-1-i)))!=0))                   return false;
        }
        next=now;
        for(int i=0;i<n;i++)
        {
            if(ed.fudetail[i]=='+')  next=next|(1<<(n-1-i));
            if(ed.fudetail[i]=='-' && ((now&(1<<(n-1-i)))==(1<<(n-1-i))))   next=next-(1<<(n-1-i));
        }
        return true;
    }
    
    void djs()
    {
        memset(vis,0,sizeof(vis));
        int b=(1<<n) -1;
        points[b].dis=0;
        Q.push(points[b]);
        while(!Q.empty())
        {
            int k=(Q.top()).th; Q.pop();
            if(vis[k]) continue;
            Po &now=points[k];vis[k]=true;
            int next;
            if(vis[0]) break;
            
            for(int i=0;i<(int)edges.size();i++)
                if(is_ok(k,i,next)&&!vis[next]&&points[next].dis>now.dis+edges[i].span)
                {
                    points[next].dis=now.dis+edges[i].span;
                    Q.push(points[next]);
                }
        }
    }
    
    int main()
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++)
        {
            int k; char st;
            scanf("%d",&k);
            edges.push_back(Ed(k));
            while((int)edges[edges.size()-1].nodetail.size()<n){
                scanf("%c",&st);
                if(st=='+'||st=='-'||st=='0')
                edges[edges.size()-1].nodetail.push_back(st);
                }
            while((int)edges[edges.size()-1].fudetail.size()<n){
                scanf("%c",&st);
                if(st=='+'||st=='-'||st=='0')
                edges[edges.size()-1].fudetail.push_back(st);
                }
        }
        for(int i=0;i<= (1<<n) -1;i++)
            points.push_back(Po(i,INF));
        
        djs();
        if(points[0].dis==INF) printf("0\n");
            else printf("%d\n",points[0].dis);
        return 0;
    }
    
  • 0
    @ 2015-10-31 12:22:16

    位运算+BFS,扩展时加判断,只有合法并且答案更优才加到队列里去,一直做到队列为空才输出答案。

    //vijos p1019
    #include <stdio.h>

    #define INF 2000000000
    #define STATUS 0
    #define STEP 1

    char function[120][20];
    char condition[120][20];
    int cost[120];

    int answer[1<<20];
    int queue[1<<20][2];
    int head, tail;

    void addToQueue(int status, int step){
    if(answer[status] > step){
    answer[status] = step;
    queue[tail][STATUS] = status;
    queue[tail][STEP] = step;
    tail++;
    }
    }
    int bfs(int numBug, int numPatch){
    int status, step, i, j, tmp, target;
    head = tail = 0;
    target = (1<<numBug) - 1; //all bugs have been fixed
    addToQueue(0, 0); //no bug has been fixed
    while(head < tail){
    status = queue[head][STATUS];
    step = queue[head][STEP];
    for(i=0; i<numPatch; i++){
    //judge if the move is legal
    tmp = 1;
    for(j=0; j<numBug; j++){
    switch(condition[i][j]){
    case '+':
    if((status>>j)&1)
    tmp = 0;
    break;
    case '-':
    if(!((status>>j)&1))
    tmp = 0;
    break;
    }
    if(tmp == 0)
    break;
    }
    if(tmp == 0) //illegal
    continue;

    //move
    tmp = status;
    for(j=0; j<numBug; j++){
    switch(function[i][j]){
    case '-':
    tmp |= (1<<j);
    break;
    case '+':
    tmp &= (target^(1<<j));
    break;
    }
    }
    addToQueue(tmp, step+cost[i]);
    }
    head++;
    }
    return answer[target]==INF ? 0:answer[target];
    }
    int main(){
    int numBug, numPatch, i;

    scanf("%d %d", &numBug, &numPatch);
    for(i=0; i<numPatch; i++)
    scanf("%d %s %s", &cost[i], condition[i], function[i]);

    for(i=0; i<(1<<numBug); i++)
    answer[i] = INF;

    printf("%d\n", bfs(numBug, numPatch));

    return 0;
    }

  • 0
    @ 2015-10-15 21:46:59

    program asddasf;
    type po=^node;
    node=record
    a,b:longint;
    c:po;
    end;
    var i,j,k,l,m,n,sum:longint;
    s2,s1:array[0..100] of string;
    a:array[0..100] of longint;
    pa:array[0..400000] of po;
    dis:array[-1..400000] of longint;
    h:array[0..800000] of longint;
    v:array[0..400000] of boolean;
    p:po;
    s,s0:ansistring;
    ch:boolean;
    function ff(x:string):longint;
    var k,l:longint;
    begin
    ff:=0;
    l:=1;
    for k:=length(x) downto 1 do
    begin
    if x[k]='1' then
    ff:=ff+l;
    l:=l*2;
    end;
    exit(ff);
    end;

    procedure chu(x1,y1:string;z1:longint);
    var k,l,k1,k2:longint;
    sn:ansistring;
    begin
    sn:=x1;
    for j:=1 to n do
    begin
    if y1[j]='+' then
    sn[j]:='1';
    if y1[j]='-' then
    sn[j]:='0';
    end;
    k1:=ff(x1);
    k2:=ff(sn);
    new(p);
    p^.a:=k2;
    p^.b:=z1;
    p^.c:=pa[k1];
    pa[k1]:=p;
    end;
    procedure sou(x,y:longint;z:string);
    var j:longint;
    begin
    if y=n+1 then
    begin
    chu(z,s2[x],a[x]);
    exit;
    end;
    if s1[x][y]='0' then
    begin
    sou(x,y+1,z+'1');
    sou(x,y+1,z+'0');
    end;
    if s1[x][y]='-' then
    sou(x,y+1,z+'0');
    if s1[x][y]='+' then
    sou(x,y+1,z+'1');
    end;

    procedure spfa(x:longint);
    var i,j,t,u,ans:longint;
    begin
    fillchar(dis,sizeof(dis),$7f div 3);
    dis[x]:=0;
    h[1]:=x;
    v[x]:=true;
    t:=0; u:=1;
    repeat
    inc(t);
    ans:=h[t];
    v[ans]:=false;
    p:=pa[ans];
    while p<>nil do
    begin
    if dis[p^.a]>dis[ans]+p^.b then
    begin
    dis[p^.a]:=dis[ans]+p^.b;
    if v[p^.a]=false then
    begin
    inc(u);
    h[u]:=p^.a;
    v[h[u]]:=true;
    end;
    end;
    p:=p^.c;
    end;
    until t=u;
    end;

    begin
    readln(n,m);
    for i:=1 to m do
    begin
    readln(s);
    j:=pos(' ',s);
    s0:=copy(s,1,j-1);
    val(s0,a[i]);
    delete(s,1,j);
    j:=pos(' ',s);
    s1[i]:=copy(s,1,j-1);
    delete(s,1,j);
    s2[i]:=s;
    end;
    for i:=1 to m do
    sou(i,1,'');
    s:='';
    for i:=1 to n do
    s:=s+'1';
    spfa(ff(s));
    if dis[0]=dis[-1] then
    writeln(0)
    else
    writeln(dis[0]);

    end.

  • 0
    @ 2014-08-24 20:51:59

    按照补丁个数进行BFS,先不考虑时间问题。
    对每个被修复的状态剪枝——如果BFS到当前状态耗时大于被记录的最小时间,就不继续BFS。
    好像数据比较弱,这样就能最多15MS过了

    int bfs(){
    int ret=iinf;
    tmp.now=0,tmp.lv=0;
    q.push(tmp);
    while(!q.empty()){
    tmp=q.front();
    q.pop();
    rep(i,0,m){
    if(!( (bb2[i] == (tmp.now|bb2[i])) && (bb1[i] == (tmp.now&bb1[i])) ))
    continue;

    ne.now=((tmp.now&ff2[i])|ff1[i]);
    ne.lv=tmp.lv+w[i];
    if(vst[ne.now]&&ne.lv>=cost[ne.now])
    continue;

    vst[ne.now]=1;
    cost[ne.now]=ne.lv;

    if(ne.now==ed)
    ret=ne.lv;
    else
    q.push(ne);
    }
    }
    return ret;
    }

  • 0
    @ 2014-02-25 22:35:55

    高兴啊,提交了9次终于TM还是让我AC了!
    测试数据 #0: Accepted, time = 0 ms, mem = 1904 KiB, score = 10
    测试数据 #1: Accepted, time = 15 ms, mem = 1904 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 1904 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 1904 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 1908 KiB, score = 10
    测试数据 #5: Accepted, time = 15 ms, mem = 1904 KiB, score = 10
    测试数据 #6: Accepted, time = 15 ms, mem = 1904 KiB, score = 10
    测试数据 #7: Accepted, time = 15 ms, mem = 1904 KiB, score = 10
    测试数据 #8: Accepted, time = 0 ms, mem = 1908 KiB, score = 10
    测试数据 #9: Accepted, time = 0 ms, mem = 1904 KiB, score = 10
    Accepted, time = 60 ms, mem = 1908 KiB, score = 100

  • 0
    @ 2014-02-19 22:37:56

    我擦,不想说了,发程序的人都TM二笔,全是编译错误

  • 0
    @ 2013-08-23 17:26:12

    编译成功

    测试数据 #0: Accepted, time = 0 ms, mem = 1264 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 1264 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 1260 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 1268 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 1264 KiB, score = 10
    测试数据 #5: Accepted, time = 0 ms, mem = 1264 KiB, score = 10
    测试数据 #6: Accepted, time = 0 ms, mem = 1264 KiB, score = 10
    测试数据 #7: Accepted, time = 0 ms, mem = 1264 KiB, score = 10
    测试数据 #8: Accepted, time = 0 ms, mem = 1264 KiB, score = 10
    测试数据 #9: Accepted, time = 0 ms, mem = 1260 KiB, score = 10
    Accepted, time = 0 ms, mem = 1268 KiB, score = 100
    纪念一下 思路和毒药类似 但没有构图觉得会超空间
    因为有使用条件 直接枚举即可 为不构图提供了条件
    BFS+位运算

  • 0
    @ 2012-09-26 20:48:38

    ├ 测试数据 01:答案正确... (0ms, 7260KB) 

    ├ 测试数据 02:答案正确... (0ms, 7260KB) 

    ├ 测试数据 03:答案正确... (0ms, 7260KB) 

    ├ 测试数据 04:答案正确... (0ms, 7260KB) 

    ├ 测试数据 05:答案正确... (0ms, 7260KB) 

    ├ 测试数据 06:答案正确... (0ms, 7260KB) 

    ├ 测试数据 07:答案正确... (0ms, 7260KB) 

    ├ 测试数据 08:答案正确... (0ms, 7260KB) 

    ├ 测试数据 09:答案正确... (0ms, 7260KB) 

    ├ 测试数据 10:答案正确... (0ms, 7260KB) 

    VIJOS这碉堡了的评测机,同样的程序测了至少6遍才AC了。。。口口声声说我的0ms是TLE。。。

  • 0
    @ 2012-08-07 00:05:23

    #01: Accepted (39ms, 504KB) 

    #02: Accepted (78ms, 504KB) 

    #03: Accepted (12ms, 504KB) 

    #04: Accepted (16ms, 504KB) 

    #05: Accepted (47ms, 504KB) 

    #06: Accepted (67ms, 504KB) 

    #07: Accepted (59ms, 504KB) 

    #08: Accepted (153ms, 504KB) 

    #09: Accepted (35ms, 508KB) 

    #10: Accepted (24ms, 508KB)

  • 0
    @ 2012-08-01 18:39:49

    编译通过... 

    ├ 测试数据 01:答案正确... 0ms 

    ├ 测试数据 02:答案正确... 0ms 

    ├ 测试数据 03:答案正确... 0ms 

    ├ 测试数据 04:答案正确... 0ms 

    ├ 测试数据 05:答案正确... 0ms 

    ├ 测试数据 06:答案正确... 0ms 

    ├ 测试数据 07:答案正确... 0ms 

    ├ 测试数据 08:答案正确... 0ms 

    ├ 测试数据 09:答案正确... 0ms 

    ├ 测试数据 10:答案正确... 0ms 

    ---|---|---|---|---|---|---|---|- 

    Accepted 有效得分:100 有效耗时:0ms 

    /*

    spfa 秒过   &&   1A

    用二进制表示状态,用数组记录第i个补丁是否可以用在状态j上(小优化)

     话说vijos上pascal是王道么?还是c++用着顺手。 

    70行代码。spfa+位运算 

    */

  • 0
    @ 2009-11-07 15:13:00

    如果用二进制数表示问题的状态,那么我们可以用0..2^n -1来表示所有的状态。

    如果一个状态可以迁移到另一个状态,那么就是说,经过一种补丁可以修改它,这一类补丁中,应当取那个时间最小的。

    然后Dijkstra,总共519ms通过。(Evolution smdCn)

信息

ID
1019
难度
5
分类
搜索 | 搜索与剪枝 点击显示
标签
递交数
1550
已通过
480
通过率
31%
被复制
5
上传者