【HDOJ】2242 考研路茫茫——空调教室-白红宇

【HDOJ】2242 考研路茫茫——空调教室

阅读量：6413 次

发布时间：2019-06-23

本文共 4655 字，大约阅读时间需要 15 分钟。

tarjan缩点，然后树形dp一下可解。重点是重边的处理。

1 /* 2242 */  2 #include 
     
        3 #include 
      
         4 #include 
       
          5 #include 
          6 #include 
         
            7 #include 
          
            8 #include 
           
             9 #include 
            
              10 #include 
             
               11 #include 
              
                12 #include 
               
                 13 #include 
                
                  14 #include 
                 
                   15 #include 
                  
                    16 #include 
                   
                     17 #include 
                    
                      18 #include 
                     
                       19 #include 
                      
                        20 #include 
                       
                         21 #include 
                        
                          22 #include 
                         
                           23 using namespace std; 24 //#pragma comment(linker,"/STACK:102400000,1024000") 25 26 #define sti set
                          
                            27 #define stpii set
                           
                            
                              > 28 #define mpii map
                             
                               29 #define vi vector
                              
                                30 #define pii pair
                               
                                 31 #define vpii vector
                                
                                 
                                   > 32 #define rep(i, a, n) for (int i=a;i
                                  
                                   =a;--i) 34 #define clr clear 35 #define pb push_back 36 #define mp make_pair 37 #define fir first 38 #define sec second 39 #define all(x) (x).begin(),(x).end() 40 #define SZ(x) ((int)(x).size()) 41 #define lson l, mid, rt<<1 42 #define rson mid+1, r, rt<<1|1 43 44 typedef struct { 45 int v, nxt; 46 } edge_t; 47 48 const int maxv = 10005; 49 const int maxe = 40005; 50 int head[maxv], l; 51 edge_t E[maxe]; 52 int low[maxv], pre[maxv], bn[maxv]; 53 int S[maxv], top; 54 int block, dfs_clock; 55 int num[maxv], tot[maxv], sum; 56 int head_[maxv], l_; 57 edge_t E_[maxe]; 58 bool visit[maxv]; 59 int n, m; 60 int ans; 61 62 void init() { 63 l = block = dfs_clock = 0; 64 top = 0; 65 memset(pre, 0, sizeof(pre)); 66 memset(bn, 0, sizeof(bn)); 67 memset(head, -1, sizeof(head)); 68 } 69 70 void init_() { 71 l_ = sum = 0; 72 memset(tot, 0, sizeof(tot)); 73 memset(head_, -1, sizeof(head_)); 74 memset(visit, false, sizeof(visit)); 75 ans = INT_MAX; 76 } 77 78 void addEdge(int u, int v) { 79 E[l].v = v; 80 E[l].nxt = head[u]; 81 head[u] = l++; 82 83 E[l].v = u; 84 E[l].nxt = head[v]; 85 head[v] = l++; 86 } 87 88 void addEdge_(int u, int v) { 89 E_[l_].v = v; 90 E_[l_].nxt = head_[u]; 91 head_[u] = l_++; 92 93 E_[l_].v = u; 94 E_[l_].nxt = head_[v]; 95 head_[v] = l_++; 96 } 97 98 void tarjan(int u, int fa) { 99 int v, k;100 bool flag = true;101 102 S[top++] = u;103 pre[u] = low[u] = ++dfs_clock;104 for (k=head[u]; k!=-1; k=E[k].nxt) {105 v = E[k].v;106 if (v == fa && flag) {107 flag = false;108 continue;109 }110 111 if (!pre[v]) {112 tarjan(v, u);113 low[u] = min(low[u], low[v]);114 } else if (!bn[v]) {115 low[u] = min(low[u], pre[v]);116 }117 }118 119 if (low[u] == pre[u]) {120 ++block;121 do {122 bn[S[--top]] = block;123 } while (S[top]!=u);124 }125 }126 127 void dfs(int u, int fa) {128 int v, k;129 130 visit[u] = true;131 for (k=head_[u]; k!=-1; k=E_[k].nxt) {132 v = E_[k].v;133 if (v==fa || visit[v])134 continue;135 dfs(v, u);136 tot[u] += tot[v];137 }138 139 ans = min(ans, abs(sum-tot[u]-tot[u]));140 }141 142 void solve() {143 rep(i, 0, n) {144 if (!pre[i])145 tarjan(i, -1);146 }147 148 #ifndef ONLINE_JUDGE149 printf("block = %d\n", block);150 #endif151 152 if (block <= 1) {153 puts("impossible");154 return ;155 }156 157 init_();158 int u, v, k;159 160 for (u=0; u

数据生成器。

1 import sys 2 import string 3 from random import randint 4  5      6 def GenData(fileName): 7     with open(fileName, "w") as fout: 8         t = 10 9         for tt in xrange(t):10             n = randint(100, 200)11             m = randint(n/10, n+n/10)12             fout.write("%d %d\n" % (n, m))13             dataList = []14             for i in xrange(n):15                 x = randint(0, 1000)16                 dataList.append(x)17             fout.write(" ".join(map(str, dataList)) + "\n")18             for i in xrange(m):19                 a = randint(0, n)20                 b = randint(0, n)21                 fout.write("%d %d\n" % (a, b))22                 23         24 def MovData(srcFileName, desFileName):25     with open(srcFileName, "r") as fin:26         lines = fin.readlines()27     with open(desFileName, "w") as fout:28         fout.write("".join(lines))29 30         31 def CompData():32     print "comp"33     srcFileName = "F:\Qt_prj\hdoj\data.out"34     desFileName = "F:\workspace\cpp_hdoj\data.out"35     srcLines = []36     desLines = []37     with open(srcFileName, "r") as fin:38         srcLines = fin.readlines()39     with open(desFileName, "r") as fin:40         desLines = fin.readlines()41     n = min(len(srcLines), len(desLines))-142     for i in xrange(n):43         ans2 = int(desLines[i])44         ans1 = int(srcLines[i])45         if ans1 > ans2:46             print "%d: wrong" % i47 48             49 if __name__ == "__main__":50     srcFileName = "F:\Qt_prj\hdoj\data.in"51     desFileName = "F:\workspace\cpp_hdoj\data.in"52     GenData(srcFileName)53     MovData(srcFileName, desFileName)54     55

转载于:https://www.cnblogs.com/bombe1013/p/5165388.html

你可能感兴趣的文章

python “双”稀疏矩阵转换为最小联通量“单”矩阵

查看>>

揭秘天猫双11背后：20万商家600万张海报，背后只有一个鹿班

查看>>

重置mysq root密码脚本

查看>>