wikioi 1002 搭桥 - c++编程基础

题意：这题刚开始看错题意了，原来桥是建在一条直线上就行，不管距离多远。

思路：dfs求第一问答案，然后最小生成树搞，不能建桥的边就设为INF就行了，然后如果用到INF的边就加上0就行了。这样跑一遍最小生成树就是答案。

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include
  
   
#include
   
     #include
    
      #include
     
       #include
       #include
       
         #include
        
          #include
         
           #include
          
            #define mem(a,b) memset(a,b,sizeof(a)) #define lson i<<1,l,mid #define rson i<<1|1,mid+1,r #define llson j<<1,l,mid #define rrson j<<1|1,mid+1,r #define INF 0x7fffffff #define maxn 55 typedef long long ll; typedef unsigned long long ull; using namespace std; int n,m,cnt,vis[maxn][maxn],mm[maxn][maxn],sum; int a[1000005],b[1000005],tmp,sum2,sum3; char s[maxn][maxn]; int dist[8][2]= {1,0,1,1,1,-1,0,1,0,-1,-1,0,-1,1,-1,-1}; int f[1000005]; void dfs(int x,int y,int ans) { for(int i=0; i<8; i++) { int xx=x+dist[i][0],yy=y+dist[i][1]; if(xx>=0&&xx
           
            =0&&yy