0_0_16386220_30906.cpp:2:13: error: #include expects "FILENAME" or <FILENAME>
#include #include #include #define N_node 120#define N_edge 22000 #define inf 1000000000 using namespace std; typedef struct{ int to ,next ,cost; }STAR; typedef struct { int x ,t; }DEP; STAR E[N_edge] ,E_[N_edge]; DEP xin ,tou; int list[N_node] ,list1[N_node] ,tot; int list2[N_node]; int deep[N_node]; int mks[N_node] ,mks_; int mkh[N_node] ,mkh_; int mark[N_node]; void add(int a ,int b ,int c) { E[++tot].to = b; E[tot].cost = c; E[tot].next = list[a]; list[a] = tot; E[++tot].to = a; E[tot].cost = 0; E[tot].next = list[b]; list[b] = tot; } int minn(int a ,int b) { return a } bool BFS_DEEP(int s ,int t ,int n) { memset(deep ,255 ,sizeof(deep)); deep[s] = 0; xin.x = s; xin.t = 0; queueq; q.push(xin); while(!q.empty()) { tou = q.front(); q.pop(); for(int k = list[tou.x] ;k ;k = E[k].next) { xin.x = E[k].to; xin.t = tou.t + 1; if(deep[xin.x] != -1 || !E[k].cost) continue; deep[xin.x] = xin.t; q.push(xin); } } for(int i = 0 ;i list1[i] = list[i]; return deep[t] != -1; } int DFS_MAX_FLOW(int s ,int t ,int flow) { if(s == t) return flow; int nowflow = 0; for(int k = list1[s] ;k ;k = E[k].next) { list1[s] = k; int to = E[k].to; int c = E[k].cost; if(deep[to] != deep[s] + 1||!E[k].cost) continue; int tmp = DFS_MAX_FLOW(to ,t ,minn(c ,flow - nowflow)); nowflow += tmp; E[k].cost -= tmp; E[k^1].cost += tmp; if(nowflow == flow) break; } if(!nowflow) deep[s] = 0; return nowflow; } int DINIC(int s ,int t ,int n) { int ans = 0; while(BFS_DEEP(s ,t ,n)) { ans += DFS_MAX_FLOW(s ,t ,inf); } return ans; } void DFS(int s) { for(int k = list[s] ;k ;k = E[k].next) { int to = E[k].to; if(mark[to] || !E[k].cost) continue; mark[to] = 1; DFS(to); } return ; } int main () { int n ,m ,i ,j ,t; int a ,b ,c; scanf("%d" ,&t); while(t--) { memset(list ,0 ,sizeof(list)); tot = 1; scanf("%d %d" ,&n ,&m); for(i = 1 ;i { scanf("%d %d %d" ,&a ,&b ,&c); add(a ,b ,c); } int ans = DINIC(1 ,n ,n); mks_ = mkh_ = 0; memset(mark ,0 ,sizeof(mark)); mark[1] = 1; DFS(1); for(i = 2 ;i if(mark[i]) mks[++mks_] = i; else mkh[++mkh_] = i; for(i = 1 ;i E_[i] = E[i]; int mktot = tot; for(i = 1 ;i list2[i] = list[i]; int max = 0; for(i = 1 ;i for(j = 1 ;j { a = mks[i] ,b = mkh[j]; for(int k = 1 ;k E[k] = E_[k]; memset(list ,0 ,sizeof(list)); for(int k = 1 ;k list[k] = list2[k]; tot = mktot; add(a ,b ,inf); int tmp = DINIC(1 ,n ,n); if(max } printf("%d\n" ,ans + max); } return 0; } 根据deep数组找源集和汇集,在残余网络上跑 31ms AC #include #include #include #define N_node 120 #define N_edge 22000 #define inf 1000000000 using namespace std; typedef struct { int to ,next ,cost; }STAR; typedef struct { int x ,t; }DEP; STAR E[N_edge] ,E_[N_edge]; DEP xin ,tou; int list[N_node] ,list1[N_node] ,tot; int list2[N_node]; int deep[N_node]; int mks[N_node] ,mks_; int mkh[N_node] ,mkh_; void add(int a ,int b ,int c) { E[++tot].to = b; E[tot].cost = c; E[tot].next = list[a]; list[a] = tot; E[++tot].to = a; E[tot].cost = 0; E[tot].next = list[b]; list[b] = tot; } int minn(int a ,int b) { return a } bool BFS_DEEP(int s ,int t ,int n) { memset(deep ,255 ,sizeof(deep)); deep[s] = 0; xin.x = s; xin.t = 0; queueq; q.push(xin); while(!q.empty()) { tou = q.front(); q.pop(); for(int k = list[tou.x] ;k ;k = E[k].next) { xin.x = E[k].to; xin.t = tou.t + 1; if(deep[xin.x] != -1 || !E[k].cost) continue; deep[xin.x] = xin.t; q.push(xin); } } for(int i = 0 ;i list1[i] = list[i]; return deep[t] != -1; } int DFS_MAX_FLOW(int s ,int t ,int flow) { if(s == t) return flow; int nowflow = 0; for(int k = list1[s] ;k ;k = E[k].next) { list1[s] = k; int to = E[k].to; int c = E[k].cost; if(deep[to] != deep[s] + 1||!E[k].cost) continue; int tmp = DFS_MAX_FLOW(to ,t ,minn(c ,flow - nowflow)); nowflow += tmp; E[k].cost -= tmp; E[k^1].cost += tmp; if(nowflow == flow) break; } if(!nowflow) deep[s] = 0; return nowflow; } int DINIC(int s ,int t ,int n) { int ans = 0; while(BFS_DEEP(s ,t ,n)) { ans += DFS_MAX_FLOW(s ,t ,inf); } return ans; } int main () { int n ,m ,i ,j ,t; int a ,b ,c; scanf("%d" ,&t); while(t--) { memset(list ,0 ,sizeof(list)); tot = 1; scanf("%d %d" ,&n ,&m); for(i = 1 ;i { scanf("%d %d %d" ,&a ,&b ,&c); add(a ,b ,c); } int ans = DINIC(1 ,n ,n); mks_ = mkh_ = 0; for(i = 2 ;i if(deep[i] != -1) mks[++mks_] = i; else mkh[++mkh_] = i; for(i = 1 ;i E_[i] = E[i]; int mktot = tot; for(i = 1 ;i list2[i] = list[i]; int max = 0; for(i = 1 ;i for(j = 1 ;j { a = mks[i] ,b = mkh[j]; for(int k = 1 ;k E[k] = E_[k]; memset(list ,0 ,sizeof(list)); for(int k = 1 ;k list[k] = list2[k]; tot = mktot; add(a ,b ,inf); int tmp = DINIC(1 ,n ,n); if(max } printf("%d\n" ,ans + max); } return 0; } 直接重新建图,深搜找源集和汇集(容易理解) 15msAC #include #include #include #define N_node 120 #define N_edge 22000 #define inf 1000000000 using namespace std; typedef struct { int to ,next ,cost; }STAR; typedef struct { int x ,t; }DEP; typedef struct { int a ,b ,c; }EDGE; STAR E[N_edge]; EDGE edge[N_edge]; DEP xin ,tou; int list[N_node] ,list1[N_node] ,tot; int deep[N_node]; int mks[N_node] ,mks_; int mkh[N_node] ,mkh_; int mark[N_node]; void add(int a ,int b ,int c) { E[++tot].to = b; E[tot].cost = c; E[tot].next = list[a]; list[a] = tot; E[++tot].to = a; E[tot].cost = 0; E[tot].next = list[b]; list[b] = tot; } int minn(int a ,int b) { return a } bool BFS_DEEP(int s ,int t ,int n) { memset(deep ,255 ,sizeof(deep)); deep[s] = 0; xin.x = s; xin.t = 0; queueq; q.push(xin); while(!q.empty()) { tou = q.front(); q.pop(); for(int k = list[tou.x] ;k ;k = E[k].next) { xin.x = E[k].to; xin.t = tou.t + 1; if(deep[xin.x] != -1 || !E[k].cost) continue; deep[xin.x] = xin.t; q.push(xin); } } for(int i = 0 ;i list1[i] = list[i]; return deep[t] != -1; } int DFS_MAX_FLOW(int s ,int t ,int flow) { if(s == t) return flow; int nowflow = 0; for(int k = list1[s] ;k ;k = E[k].next) { list1[s] = k; int to = E[k].to; int c = E[k].cost; if(deep[to] != deep[s] + 1||!E[k].cost) continue; int tmp = DFS_MAX_FLOW(to ,t ,minn(c ,flow - nowflow)); nowflow += tmp; E[k].cost -= tmp; E[k^1].cost += tmp; if(nowflow == flow) break; } if(!nowflow) deep[s] = 0; return nowflow; } int DINIC(int s ,int t ,int n) { int ans = 0; while(BFS_DEEP(s ,t ,n)) { ans += DFS_MAX_FLOW(s ,t ,inf); } return ans; } void DFS(int s) { for(int k = list[s] ;k ;k = E[k].next) { int to = E[k].to; if(mark[to] || !E[k].cost) continue; mark[to] = 1; DFS(to); } return ; } int main () { int n ,m ,i ,j ,t; int a ,b ,c; scanf("%d" ,&t); while(t--) { memset(list ,0 ,sizeof(list)); tot = 1; scanf("%d %d" ,&n ,&m); for(i = 1 ;i { scanf("%d %d %d" ,&a ,&b ,&c); add(a ,b ,c); edge[i].a = a ,edge[i].b = b ,edge[i].c = c; } int ans = DINIC(1 ,n ,n); mks_ = mkh_ = 0; memset(mark ,0 ,sizeof(mark)); mark[1] = 1; DFS(1); for(i = 2 ;i if(mark[i]) mks[++mks_] = i; else mkh[++mkh_] = i; for(i = 1 ;i for(j = 1 ;j { a = mks[i] ,b = mkh[j]; memset(list ,0 ,sizeof(list)); tot = 1; for(int k = 1 ;k add(edge[k].a ,edge[k].b ,edge[k].c); add(a ,b ,inf); int tmp = DINIC(1 ,n ,n); if(ans } printf("%d\n" ,ans); } return 0; }
^
|
