首页 > 代码库 > UVALive 6255 Kingdoms --状态搜索

UVALive 6255 Kingdoms --状态搜索

2024-07-14 20:07:34   214人阅读

题意：n个国家，给出国家间相互的债务关系，每个国家如果债务>收入就要破产，破产后该国的所有债务关系全部清除，第一个破产的国家不同有可能造成最后的没破产的国家的不同，问哪些国家有可能成为独自存活的国家。

解法：因为最多20个城市，破产与否的状态可用二进制数表示，破产为1，不破产为0，然后进行搜索，每一个dfs让一个国家破产，最后如果只剩下一个了，那么就将这个国家压入ans中。

代码：

#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <vector>using namespace std;#define N 1100007int vis[N];vector<int> ans;int n;int a[23][23];void dfs(int state,int num){    vis[state] = 1;    int i,j;    if(num == n-1)    {        for(i=0;i<n;i++)            if((state&(1<<i)) == 0)                ans.push_back(i);        return;    }    for(i=0;i<n;i++)  //枚举破产的国家    {        if((state&(1<<i)) == 0 && !vis[state|(1<<i)])        {            int debt = 0;            for(j=0;j<n;j++)            {                if((state&(1<<j)) == 0)  //还没破产                    debt += a[i][j];            }            if(debt > 0)  //欠债多                dfs(state|(1<<i),num+1);  //又破产一个        }    }}int main(){    int t,i,j;    scanf("%d",&t);    while(t--)    {        scanf("%d",&n);        for(i=0;i<n;i++)            for(j=0;j<n;j++)                scanf("%d",&a[i][j]);        memset(vis,0,sizeof(vis));        ans.clear();        dfs(0,0);        if(ans.size() == 0)            puts("0");        else        {            sort(ans.begin(),ans.end());            printf("%d",ans[0]+1);            for(i=1;i<ans.size();i++)                printf(" %d",ans[i]+1);            puts("");        }    }    return 0;}
View Code

 


联系
我们