Greedy Algorithm

今天進度 chapter 5  貪心演算法
希望明天能結束這個單元進入DP~~~^^

加油加油!!!好想進World Final!!!
距離ICPC台北站還剩26天!!!
Dream don't work unless you do!!! Fighting!!!

留言

張貼留言

這個網誌中的熱門文章

UVa 10976 Fractions Again

 1  #include <stdio.h>  2  #include <stdlib.h>  3  #include <iostream>  4  #include <algorithm>  5  #include <vector>  6  using namespace std ;  7  typedef pair < int , int > ii ;  8  int main ()  9  { 10      int n ; 11      while ( cin >> n ) 12      { 13          vector < ii > p ; 14          int ans = 0 ; 15          for ( int y = n + 1 ; y <= 2 * n ; y ++) 16          { 17  18              if (( n * y )%( y - n )== 0 ) 19           ...
閱讀完整內容

uva 10147 Highways

解題：Partial 'Minimum' Spanning Tree 將固定邊連接，再做Kruskal Code：   1  #include<stdio.h>   2  #include<stdlib.h>   3  #include<iostream>   4  #include<algorithm>   5  #include<vector>   6  #include<queue>   7  #include<math.h>   8  #include<utility>   9  #include<string.h>  10  #define MAXN 800  11  using namespace std ;  12  typedef pair < double , double > ii ;  13  int g [ MAXN ]={ 0 };  14  vector < ii > ans ;  15  int initial ()  16  {  17      for ( int i = 0 ; i < MAXN ; i ++) g [ i ]= i ;  18  }  19  int Find ( int a )  20  {  21      if ( g [ a ]!= a )  22      {  23   ...
閱讀完整內容

UVa 423 MPI Maelstrom

解題： 利用Floyd Warshall找出起點至任意點的距離，再找最大值就是答案 (p.s.和UVa 11463很像) Code： #include<stdio.h> #include<stdlib.h> #include<iostream> #include<algorithm> #include<string.h> #define INF 100000 using namespace std ; int dis [ 105 ][ 105 ]; int initial ( int n ) {     for ( int i = 1 ; i <= n ; i ++)         for ( int j = 1 ; j <= n ; j ++) dis [ i ][ j ]=( i == j )? 0 : INF ; } int Floyd ( int n ) {     for ( int k = 1 ; k <= n ; k ++)         for ( int i = 1 ; i <= n ; i ++)             for ( int j = 1 ; j <= n ; j ++)             {                 if ( dis [ i ][ k ]+ dis [ k ][ j ]< dis [ i ][ j ])     ...
閱讀完整內容