Calling Circles

 

floyd+dfs

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
        
       
      

 

昂贵的聘礼

 

关键在于枚举等级

1 #include
      
        2 #include
       
         3 #include
        
          4 #define ll long long 5 using namespace std; 6 const int maxn=110; 7 const int inf=0x3f3f3f3f; 8 int n,m; 9 struct edge10 {11     int v,w,nex;12 }e[maxn*maxn];13 int head[maxn];14 int cnt;15 int dis[maxn];16 int sta[maxn];17 int ins[maxn];18 int rk[maxn];19 20 void add(int u,int v,int w)21 {22     e[cnt].v=v;23     e[cnt].w=w;24     e[cnt].nex=head[u];25     head[u]=cnt++;26 }27 28 int  spfa(int s,int r)29 {30     for(int i=0;i<=n;i++)31     {32         dis[i]=inf;33         ins[i]=0;34     }35     dis[s]=0;36     ins[s]=1;37     int top=0;38     sta[top++]=s;39     while(top)40     {41         int u=sta[--top];42         ins[u]=0;43         for(int i=head[u];i!=-1;i=e[i].nex)44         {45             int v=e[i].v;46             if(rk[v]>m+r||rk[v]
         
          dis[u]+w)49             {50                 dis[v]=dis[u]+w;51                 if(!ins[v])52                 {53                     ins[v]=1;54                     sta[top++]=v;55                 }56             }57         }58     }59     return dis[1];60 }61 62 int main()63 {64     scanf("%d%d",&m,&n);65     int p,x,y;66     cnt=0;67     memset(head,-1,sizeof(head));68     for(int i=1;i<=n;i++)69     {70         scanf("%d%d%d",&p,&rk[i],&x);71         add(0,i,p);72         for(int j=0;j
         
        
       
      

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 using namespace std; 6 const int maxn=110; 7 const int inf=0x3f3f3f3f; 8 struct Edge{ 9     int v,w,nex;10 }e[maxn*maxn*2];11 int head[maxn];12 int cnt;13 void init(){14     memset(head,-1,sizeof(head));15     cnt=0;16 }17 void add(int u,int v,int w){18     e[cnt].v=v;19     e[cnt].w=w;20     e[cnt].nex=head[u];21     head[u]=cnt++;22 }23 int n,m;24 int r[maxn];25 typedef pair
          
            pii;26 int d[maxn];27 int dijkstra(int s,int g){28     memset(d,inf,sizeof(d));29     d[s]=0;30     pii a=pii(0,s);31     priority_queue< pii, vector
           
             ,greater
            
              > pq;32 pq.push(a);33 while(!pq.empty()){34 pii b=pq.top();35 pq.pop();36 int u=b.second;37 if(d[u]
             
              g+m||r[v]
              
               d[u]+e[i].w){42 d[v]=d[u]+e[i].w;43 pq.push(pii(d[v],v));44 }45 }46 }47 return d[1];48 }49 50 51 52 int main(){53 while(scanf("%d%d",&m,&n)!=EOF){54 init();55 int p,x;56 for(int i=1;i<=n;i++){57 scanf("%d%d%d",&p,&r[i],&x);58 add(0,i,p);59 int v;60 for(int j=0;j
              
             
            
           
          
         
        
       
      

 

 

scu4444

题目连接：

题意：n个点，其中有m条边的费用为a，其它边的费用为b，让求1到n的最小花费。m和n都<=1e5.

首先看连接1和n的是a边还是b边，分情况去计算另一种的费用，然后取较小的。

如果是a边，那么要考虑走b类边的费用，而b类边可能高达1e10条（几乎是完全图了），用bfs！用set保证每个点只入队一次！

如果是b边，考虑走a边的方案，dijkstra或者bellman_ford都可以

1 #include
       
          2 #include
        
           3 #include
         
            4 #include
          
             5 #include
           
              6 #define ll long long  7 using namespace std;  8   9 const int maxn=1e5+10; 10 const int inf=0x3f3f3f3f; 11 int head[maxn]; 12 int cnt=0; 13 ll dis[maxn]; 14  15 int n,m; 16 ll a,b; 17 int u,v; 18  19 struct edge 20 { 21     int v,w,nex; 22 }e[maxn*10]; 23 struct node 24 { 25     int v; 26     ll c; 27     bool operator <(const node&a)const 28     { 29         return c>a.c; 30     } 31 }; 32 void init() 33 { 34     cnt=0; 35    for(int i=0;i<=n;i++) 36    { 37        head[i]=-1; 38    } 39 } 40  41 void add(int u,int v,int w) 42 { 43     e[cnt].v=v; 44     e[cnt].w=w; 45     e[cnt].nex=head[u]; 46     head[u]=cnt++; 47 } 48 ll dijkstra(int n) 49 { 50    for(int i=0;i<=n;i++) 51         dis[i]=inf; 52     priority_queue
            
              pq; 53 dis[1]=0; 54 pq.push(node{ 1,0}); 55 while(!pq.empty()) 56 { 57 node temp=pq.top(); 58 pq.pop(); 59 int u=temp.v; 60 if(dis[u]
             
              dis[u]+w) 66 { 67 dis[v]=dis[u]+w; 68 pq.push(node{v,dis[v]}); 69 } 70 } 71 } 72 return dis[n]; 73 } 74 75 ll bfs(int n,ll val) 76 { 77 set
              
                ta,tb; 78 queue
               
                q; 79 q.push(1); 80 dis[1]=0; 81 dis[n]=inf; 82 for(int i=2;i<=n;i++) ta.insert(i); 83 while(!q.empty()) 84 { 85 int u=q.front(); 86 q.pop(); 87 for(int i=head[u];i!=-1;i=e[i].nex) 88 { 89 int v=e[i].v; 90 if(!ta.count(v)) continue; 91 ta.erase(v); 92 tb.insert(v); 93 } 94 for(set
                
                 ::iterator it=ta.begin();it!=ta.end();it++) 95 { 96 q.push(*it); 97 dis[*it]=dis[u]+val; 98 } 99 ta.swap(tb);100 tb.clear();101 }102 return dis[n];103 }104 int main()105 {106 107 while(scanf("%d%d%lld%lld",&n,&m,&a,&b)!=EOF)108 {109 init();110 int flag=0;111 for(int i=0;i
                
               
              
             
            
           
          
         
        
       

 

0 or 1

 

题意：题目给出了一个矩阵，其实是一个图，点i到点j的边权重为cij。让求满足1的楚都为1且n的入度为1的路径的最小值。

首先可以想到的是求最短路。

容易忽略的一种情况是1出发形成个环再回到1，n也是走一个环再回到n，也满足题意。

上述两种情况去较小的。

1 #include
       
         2 #include
        
          3 #include
         
           4 #include
          
            5 using namespace std; 6 const int maxn=350; 7 const int inf=0x3f3f3f3f; 8 int n; 9 int pic[maxn][maxn];10 int dis[maxn];11 int inq[maxn];12 void spfa(int s)13 {14 15     queue
           
             q;16     while(!q.empty()) q.pop();17     for(int i=1;i<=n;i++)              18     {19         inq[i]=0;20         if(i==s) dis[i]=inf; //求最小环21         else {22             dis[i]=pic[s][i];  //23             inq[i]=1;24             q.push(i);25         }26     }27     while(!q.empty())28     {29         int u=q.front();30         q.pop();31         inq[u]=0;32         for(int i=1;i<=n;i++)33         {34             if(dis[i]>dis[u]+pic[u][i])35             {36                 dis[i]=dis[u]+pic[u][i];37 38                 if(!inq[i])39                 {40                     inq[i]=1;41                     q.push(i);42                 }43             }44         }45     }46 47 }48 49 int main()50 {51     while(scanf("%d",&n)!=EOF&&n)52     {53         for(int i=1;i<=n;i++)54             for(int j=1;j<=n;j++)55                 scanf("%d",&pic[i][j]);56         spfa(1);57         int s1=dis[1];  //1的最小环58         int ans=dis[n];//1到n的最短路59         spfa(n);60         int s2=dis[n];// n的最小环61         ans=min(ans,s1+s2);62         printf("%d\n",ans);63     }64 }
           
          
         
        
       

 

题目连接：

首先判断图中是否存在环，若不存在则No cycle found.

若存在：

可知lowest mean的范围是介于最大权和最小权之间的。

可以二分，查找符合条件的最小值。

mid满足的条件是，存在k条边，使得w1+w2+w3+……+wk<k*mid;

上式可变形为 （w1-mid）+(w2-mid))+……+（wk-mid）<0; 即判断负环。

开始只判断了从1开始是否存在负环,WA几次才意识到问题，负环可能不含点1。。

虚拟一个结点0，到各个点距离为0. 从节点0开始入队即可查找全图是否存在负环。

1 #include
       
          2 #include
        
           3 #include
         
            4 #include
          
             5 using namespace std;  6   7 const double eps=1e-8;  8 const int inf=0x3f3f3f3f;  9 const int maxn=110; 10  11 struct edge 12 { 13     int v,nex; 14     double w; 15 }e[maxn*maxn]; 16  17 int head[maxn],cnt=0; 18 int inq[maxn],vis[maxn]; 19 double dis[maxn]; 20 int n,m; 21  22 void add(int u,int v,double w) 23 { 24     e[cnt].v=v; 25     e[cnt].w=w; 26     e[cnt].nex=head[u]; 27     head[u]=cnt++; 28 } 29 int spfa() 30 { 31     queue
           
             q; 32     for(int i=1;i<=n;i++) //虚拟节点0 33     { 34         dis[i]=0; 35         vis[i]=1; 36         inq[i]=1; 37         q.push(i); 38     } 39     while(!q.empty()) 40     { 41         int u=q.front(); 42         q.pop(); 43         inq[u]=0; 44         for(int i=head[u];i!=-1;i=e[i].nex) 45         { 46             int v=e[i].v; 47             if(dis[v]>dis[u]+e[i].w) 48             { 49                 dis[v]=dis[u]+e[i].w; 50                 if(!inq[v]) 51                 { 52                     inq[v]=1; 53                     vis[v]++; 54                     if(vis[v]>n) return 1; 55                     q.push(v); 56                 } 57             } 58         } 59     } 60     return 0; 61 } 62 int check(double x) 63 { 64     int ok=0; 65     for(int i=0;i
            
             eps) 96 { 97 double mid=L+(R-L)/2; 98 if(check(mid)) R=mid; 99 else L=mid;100 }101 printf("%.2lf\n",R);102 }103 }104 return 0;105 }
            
           
          
         
        
       

 

poj1511

题目连接：

求1到各点再回到1的最短路之和。

数据太大，只能用spfa？？

1 #include
        
          2 #include
         
           3 #include
          
            4 #include
           
             5 using namespace std; 6 #define ll long long 7 const int maxn=1000010; 8 const int inf=0x3f3f3f3f; 9 int head[maxn];10 int inq[maxn];11 ll dis[maxn];12 int n,m,t;13 int u,v,w;14 struct node15 {16     int u,v,w;17     int nex;18 }e[maxn],tmp[maxn];19 int cnt;20 21 void add(int u,int v,int w)22 {23     e[cnt].u=u;24     e[cnt].v=v;25     e[cnt].w=w;26     e[cnt].nex=head[u];27     head[u]=cnt++;28 }29 ll spfa()30 {31     stack
            
             q;32     for(int i=1;i<=n;i++)33     {34         inq[i]=0;35         dis[i]=inf;36     }37     dis[1]=0;38     inq[1]=1;39     q.push(1);40     while(!q.empty())41     {42         int x=q.top();43         q.pop();44         inq[x]=0;45         for(int i=head[x];i!=-1;i=e[i].nex)46         {47             if(dis[e[i].v]>dis[x]+e[i].w)48             {49                 dis[e[i].v]=dis[x]+e[i].w;50                 if(!inq[e[i].v])51                 {52                     q.push(e[i].v);53                     inq[e[i].v]=1;54                 }55             }56         }57     }58     ll res=0;59     for(int i=1;i<=n;i++)60         res+=dis[i];61     return res;62 }63 int main()64 {65     scanf("%d",&t);66     while(t--)67     {68         cnt=0;69         scanf("%d%d",&n,&m);70         memset(head,-1,sizeof(head));71         for(int i=0;i
            
           
          
         
        

 

Steam Roller

 

反正我是根本不会建图=_=||

看了好久大概看明白一点。。。

1 #include 
         
            2 using namespace std;  3 #define CLR(m,a) memset(m,a,sizeof(m))  4 typedef pair
          
            PII;  5 const int inf=0x3f3f3f3f;  6 const int maxv=80010;  7 const int maxe=330000;  8   9 struct Edge{ 10     int v,w; 11     int nex; 12     Edge(int v=0,int w=0,int nex=0): 13         v(v),w(w),nex(nex){} 14 }e[maxe]; 15 int head[maxv]; 16 int cnt=0; 17 void init() 18 { 19     CLR(head,-1); 20     cnt=0; 21 } 22 void add(int u,int v,int w) 23 { 24     e[cnt]=Edge(v,w,head[u]); 25     head[u]=cnt++; 26 } 27  28 int dis[maxv]; 29 void dijkstra(int s) 30 { 31     priority_queue
           
            
              ,greater
             
               > pq; 32     CLR(dis,inf); 33     dis[s]=0; 34     pq.push(PII(0,s)); 35     while(!pq.empty()){ 36         PII tp=pq.top(); 37         pq.pop(); 38         int u=tp.second; 39         if(dis[u]
              
               dis[u]+e[i].w){ 43 dis[v]=dis[u]+e[i].w; 44 pq.push(PII(dis[v],v)); 45 } 46 } 47 } 48 } 49 50 int R,C,r1,c1,r2,c2; 51 const int UP=0, LEFT=1, DOWN=2, RIGHT=3 ; //各方向的名字 52 const int inv[]={ 2,3,0,1}; //每个方向的反方向 53 const int dr[]={-1,0,1,0}; //每个方向对应的“行编号”的增量 54 const int dc[]={ 0,-1,0,1}; //每个方向对应的“列编号”的增量 55 const int maxr=100; 56 const int maxc=100; 57 58 int grid[maxr][maxc][4]; //grid[r][c][dir]代表从交叉点（r,c）出发，dir方向的边权 59 int n,id[maxr][maxc][4][2]; //节点总数，状态(r,c,dir,doubled)的编号 60 61 //给状态(r,c,dir,doubled)编号 62 int ID(int r,int c,int dir,int doubled) 63 { 64 int &x=id[r][c][dir][doubled]; 65 if(x==0) x=++n; //从1开始编号 66 return x; 67 } 68 69 //是否可以从交叉点(r,c)沿着dir方向走 70 bool cango(int r,int c,int dir) 71 { 72 if(r<0||r>=R||c<0||c>=C) return 0; 73 return grid[r][c][dir]>0; //0不可走 74 } 75 76 int readint(){ 77 int x; 78 scanf("%d",&x); 79 return x; 80 } 81 82 int main() 83 { 84 int kase=0; 85 while(scanf("%d%d%d%d%d%d",&R,&C,&r1,&c1,&r2,&c2)!=EOF&&R){ 86 init(); 87 r1--;c1--;r2--;c2--; 88 //每个方格的左上角为基准上下左右 89 for(int r=0;r