首页 > 代码库 > poj1128拓扑排序

poj1128拓扑排序

  按照硕神的说法,以无比丑的姿势 建了个图。然后裸搞 拓扑排序

#include <cstdio>#include <cstring>#include <algorithm>#include <climits>#include <string>#include <iostream>#include <map>#include <cstdlib>#include <list>#include <set>#include <queue>#include <stack>#include<math.h>using namespace std;struct Node{    int l;int r;int up;int down;}node[1111111];int sum;const int INF=0xfffffff;int Map[100][100];int out[100];int in[100];int path[1000];int vis[1000];int vis1[1111];void dfs(int cnt){    if(cnt==sum){        for(int i =0 ;i< sum;i++)            printf("%c",path[i]+A);        cout<<endl;        return ;    }    for(int i =0 ;i<26;i++){        if(vis[i]&&out[i]==0&&!vis1[i]){            vis1[i]=1;            path[cnt]=i;            for(int j=0;j<26;j++){                if(Map[j][i]) out[j]--;            }            dfs(cnt+1);            for(int j=0;j<26;j++){                if(Map[j][i]) out[j]++;            }            vis1[i]=0;        }    }}int main(){    int n,m;    char str[100][1111];    while( cin>>n>>m){    sum=0;    memset(Map,0,sizeof(Map));    memset(out,0,sizeof(out));    memset(in, 0,sizeof(in));    memset(vis,0,sizeof(vis));    memset(vis1,0,sizeof(vis1));    for(int i = 0 ;i< 100;i++){        node[i].down=INF;node[i].up=0;node[i].r=0;node[i].l=INF;    }    for(int i =0 ;i<n;i++)        scanf("%s",str[i]);    for(int i =0 ;i<n;i++){        for(int j=0;j<m;j++){            if(str[i][j]>Z||str[i][j]<A)continue;            int t=str[i][j]-A;            if(i<node[t].down) node[t].down = i;            if(i>node[t].up) node[t].up=i;            if(j>node[t].r) node[t].r= j;            if(j<node[t].l) node[t].l=j;            vis[t]=1;        }    }    for(int i= 0;i<26;i++)        if(vis[i]) sum++;    for(int t=0;t<26;t++){        if(!vis[t]) continue;        int l=node[t].l;int r=node[t].r;int up=node[t].up;int down = node[t].down;        int i = down;        for(int j = l;j<=r;j++){            if(str[i][j]>Z||str[i][j]<A)continue;            int cc=str[i][j]-A;            if(cc!=t&&!Map[cc][t]) {                Map[cc][t]= 1;                out[cc]++;            }        }        i=up;        for(int j =l;j<=r;j++){            if(str[i][j]>Z||str[i][j]<A)continue;            int cc=str[i][j]-A;            if(cc!=t&&!Map[cc][t]) {                Map[cc][t]= 1;                out[cc]++;            }        }        int j= l;        for(int i = down+1;i<up;i++){            if(str[i][j]>Z||str[i][j]<A)continue;            int cc=str[i][j]-A;            if(cc!=t&&!Map[cc][t]) {                Map[cc][t]= 1;                out[cc]++;            }        }        j= r;        for(int i = down+1;i<up;i++){            if(str[i ][j]>Z||str[i][j]<A)continue;            int cc=str[i][j]-A;            if(cc!=t&&!Map[cc][t]) {                Map[cc][t]= 1;                out[cc]++;            }        }    }    dfs(0);    }    return 0;}