首页 > 代码库 > HDOJ 4888 Redraw Beautiful Drawings && HDOJ 4975 A simple Gaussian elimination problem
HDOJ 4888 Redraw Beautiful Drawings && HDOJ 4975 A simple Gaussian elimination problem
解题思路:
这两道题题目大致相同,都是已知一个矩阵每一行的和和每一列的和,并且每个点的数小于K 还原原矩阵并判断答案是否唯一。建图方式相同,新建一个原点S 和一个汇点T ,S到行连边,容量为该行之和,列到T连边,容量为该列之和, 对于每一个点 i 和 j ,i 行向 j 列连边 , 容量为K , 求一遍最大流。并且通过判断是否存在环来判断是否唯一。
区别在于 第二道题N 与 M 均扩大,找环需要采用更高效的算法,这里采用Tarjan 算法来找环。
HDOJ 4888
#include <iostream> #include <cstring> #include <cstdlib> #include <cstdio> #include <algorithm> #include <cmath> #include <vector> #include <queue> #include <stack> #define LL long long using namespace std; const int maxn = 10000 + 10; const int INF = 100000000; struct Edge { int from,to,cap,flow; Edge(int u,int v,int c,int w):from(u),to(v),cap(c),flow(w){ } }; int n , s , t; vector<Edge> edges; vector<int> G[maxn]; bool vis[maxn]; int d[maxn]; int cur[maxn]; void init() { for(int i=0;i<=n+1;i++) G[i].clear(); edges.clear(); } void AddEdge(int from,int to,int cap) { edges.push_back(Edge(from,to,cap,0)); edges.push_back(Edge(to,from,0,0)); int M = edges.size(); G[from].push_back(M-2); G[to].push_back(M-1); } bool BFS() { memset(vis,0,sizeof(vis)); queue<int>Q; Q.push(s); d[s] = 0; vis[s] = 1; while(!Q.empty()) { int x = Q.front();Q.pop(); for(int i=0;i<G[x].size();i++) { Edge& e = edges[G[x][i]]; if(!vis[e.to] && e.cap > e.flow) { vis[e.to] = 1; d[e.to] = d[x] + 1; Q.push(e.to); } } } return vis[t]; } int DFS(int x,int a) { if(x == t || a == 0) return a; int flow = 0 , f; for(int &i = cur[x];i<G[x].size();i++) { Edge& e = edges[G[x][i]]; if(d[x] + 1 == d[e.to] && (f = DFS(e.to,min(a,e.cap-e.flow))) > 0) { e.flow += f; edges[G[x][i]^1].flow -= f; flow += f; a -= f; if(a == 0) break; } } return flow; } int Maxflow() { int flow = 0; while(BFS()) { memset(cur,0,sizeof(cur)); flow += DFS(s,INF); } return flow; } int pre[maxn] , lowlink[maxn] ,sccno[maxn] , fa[maxn], dfs_clock , scc_cnt , flag; stack<int> S; void dfs(int u) { pre[u] = lowlink[u] = ++dfs_clock; S.push(u); for(int i=0;i<G[u].size();i++) { Edge& e = edges[G[u][i]]; if(e.cap == e.flow) continue; int v = e.to; if(!pre[v]) { fa[v] = u; dfs(v); if(!flag) return ; lowlink[u] = min(lowlink[u] , lowlink[v]); } else if(!sccno[v]) { lowlink[u] = min(lowlink[u] , pre[v]); if(v != fa[u]) {flag = 0 ; return ;} } } if(lowlink[u] == pre[u]) { scc_cnt++; for(;;) { int x = S.top(); S.pop(); sccno[x] = scc_cnt; if(x == u) break; } } } bool find_scc() { dfs_clock = scc_cnt = 0; flag = 1; memset(pre , 0, sizeof(pre)); memset(lowlink , 0, sizeof(lowlink)); memset(sccno , 0 , sizeof(sccno)); for(int i=0;i<n;i++) if(!pre[i]) { dfs(i); if(!flag) return 0;} return 1; } int main() { int T; int N , M , K; while(scanf("%d%d%d",&N,&M,&K)!=EOF) { s = 0 , t = N + M + 1; n = t + 1; init(); int sumr = 0 , sumc = 0; int x; for(int i=1;i<=N;i++) { scanf("%d",&x); AddEdge(s , i , x); sumr += x; } for(int i=1;i<=M;i++) { scanf("%d",&x); AddEdge(i + N , t , x); sumc += x; } if (sumr != sumc){ printf("Impossible\n");continue; } for(int i=1;i<=N;i++) { for(int j=1;j<=M;j++) { AddEdge(i , j + N , K); } } int ans = Maxflow(); if(ans != sumr) { printf("Impossible\n"); continue; } if(find_scc()) { printf("Unique\n"); for(int i=1;i<=N;i++) { for(int j=1;j<=M;j++) { Edge& e = edges[G[i][j]]; cout<<e.flow; if(j < M) cout<<' '; } cout<<endl; } } else printf("Not Unique\n"); } return 0; }
HDOJ 4975
<span style="color:#0000ff;">#include <iostream> #include <cstring> #include <cstdlib> #include <cstdio> #include <algorithm> #include <cmath> #include <vector> #include <queue> #include <stack> #define LL long long </span><strong><span style="color:#0000ff;">using namespace</span></strong> std<strong><span style="color:#ff00ff;">;</span><span style="color:#0000ff;"> const</span><span style="color:blue;"> int</span></strong> maxn<strong><span style="color:#ff00ff;"> =</span></strong><span style="color:#cc3300;"> 10000</span><strong><span style="color:#ff00ff;"> +</span></strong><span style="color:#cc3300;"> 10</span><strong><span style="color:#ff00ff;">;</span><span style="color:#0000ff;"> const</span><span style="color:blue;"> int</span></strong> INF<strong><span style="color:#ff00ff;"> =</span></strong><span style="color:#cc3300;"> 100000000</span><strong><span style="color:#ff00ff;">;</span><span style="color:#0000ff;"> struct</span></strong> Edge<strong><span style="color:#ff00ff;"> {</span><span style="color:blue;"> int</span></strong> from<strong><span style="color:#ff00ff;">,</span></strong>to<strong><span style="color:#ff00ff;">,</span></strong>cap<strong><span style="color:#ff00ff;">,</span></strong>flow<strong><span style="color:#ff00ff;">;</span></strong> Edge<strong><span style="color:#ff00ff;">(</span><span style="color:blue;">int</span></strong> u<strong><span style="color:#ff00ff;">,</span><span style="color:blue;">int</span></strong> v<strong><span style="color:#ff00ff;">,</span><span style="color:blue;">int</span></strong> c<strong><span style="color:#ff00ff;">,</span><span style="color:blue;">int</span></strong> w<strong><span style="color:#ff00ff;">):</span></strong>from<strong><span style="color:#ff00ff;">(</span></strong>u<strong><span style="color:#ff00ff;">),</span></strong>to<strong><span style="color:#ff00ff;">(</span></strong>v<strong><span style="color:#ff00ff;">),</span></strong>cap<strong><span style="color:#ff00ff;">(</span></strong>c<strong><span style="color:#ff00ff;">),</span></strong>flow<strong><span style="color:#ff00ff;">(</span></strong>w<strong><span style="color:#ff00ff;">){ } };</span><span style="color:blue;"> int</span></strong> n<strong><span style="color:#ff00ff;"> ,</span></strong> s<strong><span style="color:#ff00ff;"> ,</span></strong> t<strong><span style="color:#ff00ff;">;</span></strong> vector<strong><span style="color:#ff00ff;"><</span></strong>Edge<strong><span style="color:#ff00ff;">></span></strong> edges<strong><span style="color:#ff00ff;">;</span></strong> vector<strong><span style="color:#ff00ff;"><</span><span style="color:blue;">int</span><span style="color:#ff00ff;">></span></strong> G<strong><span style="color:#ff00ff;">[</span></strong>maxn<strong><span style="color:#ff00ff;">];</span><span style="color:blue;"> bool</span></strong> vis<strong><span style="color:#ff00ff;">[</span></strong>maxn<strong><span style="color:#ff00ff;">];</span><span style="color:blue;"> int</span></strong> d<strong><span style="color:#ff00ff;">[</span></strong>maxn<strong><span style="color:#ff00ff;">];</span><span style="color:blue;"> int</span></strong> cur<strong><span style="color:#ff00ff;">[</span></strong>maxn<strong><span style="color:#ff00ff;">];</span><span style="color:blue;"> void</span></strong> init<strong><span style="color:#ff00ff;">() {</span><span style="color:#0000ff;"> for</span><span style="color:#ff00ff;">(</span><span style="color:blue;">int</span></strong> i<strong><span style="color:#ff00ff;">=</span></strong><span style="color:#cc3300;">0</span><strong><span style="color:#ff00ff;">;</span></strong>i<strong><span style="color:#ff00ff;"><=</span></strong>n<strong><span style="color:#ff00ff;">+</span></strong><span style="color:#cc3300;">1</span><strong><span style="color:#ff00ff;">;</span></strong>i<strong><span style="color:#ff00ff;">++)</span></strong> G<strong><span style="color:#ff00ff;">[</span></strong>i<strong><span style="color:#ff00ff;">].</span></strong>clear<strong><span style="color:#ff00ff;">();</span></strong> edges<strong><span style="color:#ff00ff;">.</span></strong>clear<strong><span style="color:#ff00ff;">(); }</span><span style="color:blue;"> void</span></strong> AddEdge<strong><span style="color:#ff00ff;">(</span><span style="color:blue;">int</span></strong> from<strong><span style="color:#ff00ff;">,</span><span style="color:blue;">int</span></strong> to<strong><span style="color:#ff00ff;">,</span><span style="color:blue;">int</span></strong> cap<strong><span style="color:#ff00ff;">) {</span></strong> edges<strong><span style="color:#ff00ff;">.</span></strong>push_back<strong><span style="color:#ff00ff;">(</span></strong>Edge<strong><span style="color:#ff00ff;">(</span></strong>from<strong><span style="color:#ff00ff;">,</span></strong>to<strong><span style="color:#ff00ff;">,</span></strong>cap<strong><span style="color:#ff00ff;">,</span></strong><span style="color:#cc3300;">0</span><strong><span style="color:#ff00ff;">));</span></strong> edges<strong><span style="color:#ff00ff;">.</span></strong>push_back<strong><span style="color:#ff00ff;">(</span></strong>Edge<strong><span style="color:#ff00ff;">(</span></strong>to<strong><span style="color:#ff00ff;">,</span></strong>from<strong><span style="color:#ff00ff;">,</span></strong><span style="color:#cc3300;">0</span><strong><span style="color:#ff00ff;">,</span></strong><span style="color:#cc3300;">0</span><strong><span style="color:#ff00ff;">));</span><span style="color:blue;"> int</span></strong> M<strong><span style="color:#ff00ff;"> =</span></strong> edges<strong><span style="color:#ff00ff;">.</span></strong>size<strong><span style="color:#ff00ff;">();</span></strong> G<strong><span style="color:#ff00ff;">[</span></strong>from<strong><span style="color:#ff00ff;">].</span></strong>push_back<strong><span style="color:#ff00ff;">(</span></strong>M<strong><span style="color:#ff00ff;">-</span></strong><span style="color:#cc3300;">2</span><strong><span style="color:#ff00ff;">);</span></strong> G<strong><span style="color:#ff00ff;">[</span></strong>to<strong><span style="color:#ff00ff;">].</span></strong>push_back<strong><span style="color:#ff00ff;">(</span></strong>M<strong><span style="color:#ff00ff;">-</span></strong><span style="color:#cc3300;">1</span><strong><span style="color:#ff00ff;">); }</span><span style="color:blue;"> bool</span></strong> BFS<strong><span style="color:#ff00ff;">() {</span></strong> memset<strong><span style="color:#ff00ff;">(</span></strong>vis<strong><span style="color:#ff00ff;">,</span></strong><span style="color:#cc3300;">0</span><strong><span style="color:#ff00ff;">,</span><span style="color:#0000ff;">sizeof</span><span style="color:#ff00ff;">(</span></strong>vis<strong><span style="color:#ff00ff;">));</span></strong> queue<strong><span style="color:#ff00ff;"><</span><span style="color:blue;">int</span><span style="color:#ff00ff;">></span></strong>Q<strong><span style="color:#ff00ff;">;</span></strong> Q<strong><span style="color:#ff00ff;">.</span></strong>push<strong><span style="color:#ff00ff;">(</span></strong>s<strong><span style="color:#ff00ff;">);</span></strong> d<strong><span style="color:#ff00ff;">[</span></strong>s<strong><span style="color:#ff00ff;">] =</span></strong><span style="color:#cc3300;"> 0</span><strong><span style="color:#ff00ff;">;</span></strong> vis<strong><span style="color:#ff00ff;">[</span></strong>s<strong><span style="color:#ff00ff;">] =</span></strong><span style="color:#cc3300;"> 1</span><strong><span style="color:#ff00ff;">;</span><span style="color:#0000ff;"> while</span><span style="color:#ff00ff;">(!</span></strong>Q<strong><span style="color:#ff00ff;">.</span></strong>empty<strong><span style="color:#ff00ff;">()) {</span><span style="color:blue;"> int</span></strong> x<strong><span style="color:#ff00ff;"> =</span></strong> Q<strong><span style="color:#ff00ff;">.</span></strong>front<strong><span style="color:#ff00ff;">();</span></strong>Q<strong><span style="color:#ff00ff;">.</span></strong>pop<strong><span style="color:#ff00ff;">();</span><span style="color:#0000ff;"> for</span><span style="color:#ff00ff;">(</span><span style="color:blue;">int</span></strong> i<strong><span style="color:#ff00ff;">=</span></strong><span style="color:#cc3300;">0</span><strong><span style="color:#ff00ff;">;</span></strong>i<strong><span style="color:#ff00ff;"><</span></strong>G<strong><span style="color:#ff00ff;">[</span></strong>x<strong><span style="color:#ff00ff;">].</span></strong>size<strong><span style="color:#ff00ff;">();</span></strong>i<strong><span style="color:#ff00ff;">++) {</span></strong> Edge<strong><span style="color:#ff00ff;">&</span></strong> e<strong><span style="color:#ff00ff;"> =</span></strong> edges<strong><span style="color:#ff00ff;">[</span></strong>G<strong><span style="color:#ff00ff;">[</span></strong>x<strong><span style="color:#ff00ff;">][</span></strong>i<strong><span style="color:#ff00ff;">]];</span><span style="color:#0000ff;"> if</span><span style="color:#ff00ff;">(!</span></strong>vis<strong><span style="color:#ff00ff;">[</span></strong>e<strong><span style="color:#ff00ff;">.</span></strong>to<strong><span style="color:#ff00ff;">] &&</span></strong> e<strong><span style="color:#ff00ff;">.</span></strong>cap<strong><span style="color:#ff00ff;"> ></span></strong> e<strong><span style="color:#ff00ff;">.</span></strong>flow<strong><span style="color:#ff00ff;">) {</span></strong> vis<strong><span style="color:#ff00ff;">[</span></strong>e<strong><span style="color:#ff00ff;">.</span></strong>to<strong><span style="color:#ff00ff;">] =</span></strong><span style="color:#cc3300;"> 1</span><strong><span style="color:#ff00ff;">;</span></strong> d<strong><span style="color:#ff00ff;">[</span></strong>e<strong><span style="color:#ff00ff;">.</span></strong>to<strong><span style="color:#ff00ff;">] =</span></strong> d<strong><span style="color:#ff00ff;">[</span></strong>x<strong><span style="color:#ff00ff;">] +</span></strong><span style="color:#cc3300;"> 1</span><strong><span style="color:#ff00ff;">;</span></strong> Q<strong><span style="color:#ff00ff;">.</span></strong>push<strong><span style="color:#ff00ff;">(</span></strong>e<strong><span style="color:#ff00ff;">.</span></strong>to<strong><span style="color:#ff00ff;">); } } }</span><span style="color:#0000ff;"> return</span></strong> vis<strong><span style="color:#ff00ff;">[</span></strong>t<strong><span style="color:#ff00ff;">]; }</span><span style="color:blue;"> int</span></strong> DFS<strong><span style="color:#ff00ff;">(</span><span style="color:blue;">int</span></strong> x<strong><span style="color:#ff00ff;">,</span><span style="color:blue;">int</span></strong> a<strong><span style="color:#ff00ff;">) {</span><span style="color:#0000ff;"> if</span><span style="color:#ff00ff;">(</span></strong>x<strong><span style="color:#ff00ff;"> ==</span></strong> t<strong><span style="color:#ff00ff;"> ||</span></strong> a<strong><span style="color:#ff00ff;"> ==</span></strong><span style="color:#cc3300;"> 0</span><strong><span style="color:#ff00ff;">)</span><span style="color:#0000ff;"> return</span></strong> a<strong><span style="color:#ff00ff;">;</span><span style="color:blue;"> int</span></strong> flow<strong><span style="color:#ff00ff;"> =</span></strong><span style="color:#cc3300;"> 0</span><strong><span style="color:#ff00ff;"> ,</span></strong> f<strong><span style="color:#ff00ff;">;</span><span style="color:#0000ff;"> for</span><span style="color:#ff00ff;">(</span><span style="color:blue;">int</span><span style="color:#ff00ff;"> &</span></strong>i<strong><span style="color:#ff00ff;"> =</span></strong> cur<strong><span style="color:#ff00ff;">[</span></strong>x<strong><span style="color:#ff00ff;">];</span></strong>i<strong><span style="color:#ff00ff;"><</span></strong>G<strong><span style="color:#ff00ff;">[</span></strong>x<strong><span style="color:#ff00ff;">].</span></strong>size<strong><span style="color:#ff00ff;">();</span></strong>i<strong><span style="color:#ff00ff;">++) {</span></strong> Edge<strong><span style="color:#ff00ff;">&</span></strong> e<strong><span style="color:#ff00ff;"> =</span></strong> edges<strong><span style="color:#ff00ff;">[</span></strong>G<strong><span style="color:#ff00ff;">[</span></strong>x<strong><span style="color:#ff00ff;">][</span></strong>i<strong><span style="color:#ff00ff;">]];</span><span style="color:#0000ff;"> if</span><span style="color:#ff00ff;">(</span></strong>d<strong><span style="color:#ff00ff;">[</span></strong>x<strong><span style="color:#ff00ff;">] +</span></strong><span style="color:#cc3300;"> 1</span><strong><span style="color:#ff00ff;"> ==</span></strong> d<strong><span style="color:#ff00ff;">[</span></strong>e<strong><span style="color:#ff00ff;">.</span></strong>to<strong><span style="color:#ff00ff;">] && (</span></strong>f<strong><span style="color:#ff00ff;"> =</span></strong> DFS<strong><span style="color:#ff00ff;">(</span></strong>e<strong><span style="color:#ff00ff;">.</span></strong>to<strong><span style="color:#ff00ff;">,</span></strong>min<strong><span style="color:#ff00ff;">(</span></strong>a<strong><span style="color:#ff00ff;">,</span></strong>e<strong><span style="color:#ff00ff;">.</span></strong>cap<strong><span style="color:#ff00ff;">-</span></strong>e<strong><span style="color:#ff00ff;">.</span></strong>flow<strong><span style="color:#ff00ff;">))) ></span></strong><span style="color:#cc3300;"> 0</span><strong><span style="color:#ff00ff;">) {</span></strong> e<strong><span style="color:#ff00ff;">.</span></strong>flow<strong><span style="color:#ff00ff;"> +=</span></strong> f<strong><span style="color:#ff00ff;">;</span></strong> edges<strong><span style="color:#ff00ff;">[</span></strong>G<strong><span style="color:#ff00ff;">[</span></strong>x<strong><span style="color:#ff00ff;">][</span></strong>i<strong><span style="color:#ff00ff;">]^</span></strong><span style="color:#cc3300;">1</span><strong><span style="color:#ff00ff;">].</span></strong>flow<strong><span style="color:#ff00ff;"> -=</span></strong> f<strong><span style="color:#ff00ff;">;</span></strong> flow<strong><span style="color:#ff00ff;"> +=</span></strong> f<strong><span style="color:#ff00ff;">;</span></strong> a<strong><span style="color:#ff00ff;"> -=</span></strong> f<strong><span style="color:#ff00ff;">;</span><span style="color:#0000ff;"> if</span><span style="color:#ff00ff;">(</span></strong>a<strong><span style="color:#ff00ff;"> ==</span></strong><span style="color:#cc3300;"> 0</span><strong><span style="color:#ff00ff;">)</span><span style="color:#0000ff;"> break</span><span style="color:#ff00ff;">; } }</span><span style="color:#0000ff;"> return</span></strong> flow<strong><span style="color:#ff00ff;">; }</span><span style="color:blue;"> int</span></strong> Maxflow<strong><span style="color:#ff00ff;">() {</span><span style="color:blue;"> int</span></strong> flow<strong><span style="color:#ff00ff;"> =</span></strong><span style="color:#cc3300;"> 0</span><strong><span style="color:#ff00ff;">;</span><span style="color:#0000ff;"> while</span><span style="color:#ff00ff;">(</span></strong>BFS<strong><span style="color:#ff00ff;">()) {</span></strong> memset<strong><span style="color:#ff00ff;">(</span></strong>cur<strong><span style="color:#ff00ff;">,</span></strong><span style="color:#cc3300;">0</span><strong><span style="color:#ff00ff;">,</span><span style="color:#0000ff;">sizeof</span><span style="color:#ff00ff;">(</span></strong>cur<strong><span style="color:#ff00ff;">));</span></strong> flow<strong><span style="color:#ff00ff;"> +=</span></strong> DFS<strong><span style="color:#ff00ff;">(</span></strong>s<strong><span style="color:#ff00ff;">,</span></strong>INF<strong><span style="color:#ff00ff;">); }</span><span style="color:#0000ff;"> return</span></strong> flow<strong><span style="color:#ff00ff;">; }</span><span style="color:blue;"> int</span></strong> pre<strong><span style="color:#ff00ff;">[</span></strong>maxn<strong><span style="color:#ff00ff;">] ,</span></strong> lowlink<strong><span style="color:#ff00ff;">[</span></strong>maxn<strong><span style="color:#ff00ff;">] ,</span></strong>sccno<strong><span style="color:#ff00ff;">[</span></strong>maxn<strong><span style="color:#ff00ff;">] ,</span></strong> fa<strong><span style="color:#ff00ff;">[</span></strong>maxn<strong><span style="color:#ff00ff;">],</span></strong> dfs_clock<strong><span style="color:#ff00ff;"> ,</span></strong> scc_cnt<strong><span style="color:#ff00ff;"> ,</span></strong> flag<strong><span style="color:#ff00ff;">;</span></strong> stack<strong><span style="color:#ff00ff;"><</span><span style="color:blue;">int</span><span style="color:#ff00ff;">></span></strong> S<strong><span style="color:#ff00ff;">;</span><span style="color:blue;"> void</span></strong> dfs<strong><span style="color:#ff00ff;">(</span><span style="color:blue;">int</span></strong> u<strong><span style="color:#ff00ff;">) {</span></strong> pre<strong><span style="color:#ff00ff;">[</span></strong>u<strong><span style="color:#ff00ff;">] =</span></strong> lowlink<strong><span style="color:#ff00ff;">[</span></strong>u<strong><span style="color:#ff00ff;">] = ++</span></strong>dfs_clock<strong><span style="color:#ff00ff;">;</span></strong> S<strong><span style="color:#ff00ff;">.</span></strong>push<strong><span style="color:#ff00ff;">(</span></strong>u<strong><span style="color:#ff00ff;">);</span><span style="color:#0000ff;"> for</span><span style="color:#ff00ff;">(</span><span style="color:blue;">int</span></strong> i<strong><span style="color:#ff00ff;">=</span></strong><span style="color:#cc3300;">0</span><strong><span style="color:#ff00ff;">;</span></strong>i<strong><span style="color:#ff00ff;"><</span></strong>G<strong><span style="color:#ff00ff;">[</span></strong>u<strong><span style="color:#ff00ff;">].</span></strong>size<strong><span style="color:#ff00ff;">();</span></strong>i<strong><span style="color:#ff00ff;">++) {</span></strong> Edge<strong><span style="color:#ff00ff;">&</span></strong> e<strong><span style="color:#ff00ff;"> =</span></strong> edges<strong><span style="color:#ff00ff;">[</span></strong>G<strong><span style="color:#ff00ff;">[</span></strong>u<strong><span style="color:#ff00ff;">][</span></strong>i<strong><span style="color:#ff00ff;">]];</span><span style="color:#0000ff;"> if</span><span style="color:#ff00ff;">(</span></strong>e<strong><span style="color:#ff00ff;">.</span></strong>cap<strong><span style="color:#ff00ff;"> ==</span></strong> e<strong><span style="color:#ff00ff;">.</span></strong>flow<strong><span style="color:#ff00ff;">)</span><span style="color:#0000ff;"> continue</span><span style="color:#ff00ff;">;</span><span style="color:blue;"> int</span></strong> v<strong><span style="color:#ff00ff;"> =</span></strong> e<strong><span style="color:#ff00ff;">.</span></strong>to<strong><span style="color:#ff00ff;">;</span><span style="color:#0000ff;"> if</span><span style="color:#ff00ff;">(!</span></strong>pre<strong><span style="color:#ff00ff;">[</span></strong>v<strong><span style="color:#ff00ff;">]) {</span></strong> fa<strong><span style="color:#ff00ff;">[</span></strong>v<strong><span style="color:#ff00ff;">] =</span></strong> u<strong><span style="color:#ff00ff;">;</span></strong> dfs<strong><span style="color:#ff00ff;">(</span></strong>v<strong><span style="color:#ff00ff;">);</span><span style="color:#0000ff;"> if</span><span style="color:#ff00ff;">(!</span></strong>flag<strong><span style="color:#ff00ff;">)</span><span style="color:#0000ff;"> return</span><span style="color:#ff00ff;"> ;</span></strong> lowlink<strong><span style="color:#ff00ff;">[</span></strong>u<strong><span style="color:#ff00ff;">] =</span></strong> min<strong><span style="color:#ff00ff;">(</span></strong>lowlink<strong><span style="color:#ff00ff;">[</span></strong>u<strong><span style="color:#ff00ff;">] ,</span></strong> lowlink<strong><span style="color:#ff00ff;">[</span></strong>v<strong><span style="color:#ff00ff;">]); }</span><span style="color:#0000ff;"> else if</span><span style="color:#ff00ff;">(!</span></strong>sccno<strong><span style="color:#ff00ff;">[</span></strong>v<strong><span style="color:#ff00ff;">]) {</span></strong> lowlink<strong><span style="color:#ff00ff;">[</span></strong>u<strong><span style="color:#ff00ff;">] =</span></strong> min<strong><span style="color:#ff00ff;">(</span></strong>lowlink<strong><span style="color:#ff00ff;">[</span></strong>u<strong><span style="color:#ff00ff;">] ,</span></strong> pre<strong><span style="color:#ff00ff;">[</span></strong>v<strong><span style="color:#ff00ff;">]);</span><span style="color:#0000ff;"> if</span><span style="color:#ff00ff;">(</span></strong>v<strong><span style="color:#ff00ff;"> !=</span></strong> fa<strong><span style="color:#ff00ff;">[</span></strong>u<strong><span style="color:#ff00ff;">]) {</span></strong>flag<strong><span style="color:#ff00ff;"> =</span></strong><span style="color:#cc3300;"> 0</span><strong><span style="color:#ff00ff;"> ;</span><span style="color:#0000ff;"> return</span><span style="color:#ff00ff;"> ;} } }</span><span style="color:#0000ff;"> if</span><span style="color:#ff00ff;">(</span></strong>lowlink<strong><span style="color:#ff00ff;">[</span></strong>u<strong><span style="color:#ff00ff;">] ==</span></strong> pre<strong><span style="color:#ff00ff;">[</span></strong>u<strong><span style="color:#ff00ff;">]) {</span></strong> scc_cnt<strong><span style="color:#ff00ff;">++;</span><span style="color:#0000ff;"> for</span><span style="color:#ff00ff;">(;;) {</span><span style="color:blue;"> int</span></strong> x<strong><span style="color:#ff00ff;"> =</span></strong> S<strong><span style="color:#ff00ff;">.</span></strong>top<strong><span style="color:#ff00ff;">();</span></strong> S<strong><span style="color:#ff00ff;">.</span></strong>pop<strong><span style="color:#ff00ff;">();</span></strong> sccno<strong><span style="color:#ff00ff;">[</span></strong>x<strong><span style="color:#ff00ff;">] =</span></strong> scc_cnt<strong><span style="color:#ff00ff;">;</span><span style="color:#0000ff;"> if</span><span style="color:#ff00ff;">(</span></strong>x<strong><span style="color:#ff00ff;"> ==</span></strong> u<strong><span style="color:#ff00ff;">)</span><span style="color:#0000ff;"> break</span><span style="color:#ff00ff;">; } } }</span><span style="color:blue;"> bool</span></strong> find_scc<strong><span style="color:#ff00ff;">() {</span></strong> dfs_clock<strong><span style="color:#ff00ff;"> =</span></strong> scc_cnt<strong><span style="color:#ff00ff;"> =</span></strong><span style="color:#cc3300;"> 0</span><strong><span style="color:#ff00ff;">;</span></strong> flag<strong><span style="color:#ff00ff;"> =</span></strong><span style="color:#cc3300;"> 1</span><strong><span style="color:#ff00ff;">;</span></strong> memset<strong><span style="color:#ff00ff;">(</span></strong>pre<strong><span style="color:#ff00ff;"> ,</span></strong><span style="color:#cc3300;"> 0</span><strong><span style="color:#ff00ff;">,</span><span style="color:#0000ff;"> sizeof</span><span style="color:#ff00ff;">(</span></strong>pre<strong><span style="color:#ff00ff;">));</span></strong> memset<strong><span style="color:#ff00ff;">(</span></strong>lowlink<strong><span style="color:#ff00ff;"> ,</span></strong><span style="color:#cc3300;"> 0</span><strong><span style="color:#ff00ff;">,</span><span style="color:#0000ff;"> sizeof</span><span style="color:#ff00ff;">(</span></strong>lowlink<strong><span style="color:#ff00ff;">));</span></strong> memset<strong><span style="color:#ff00ff;">(</span></strong>sccno<strong><span style="color:#ff00ff;"> ,</span></strong><span style="color:#cc3300;"> 0</span><strong><span style="color:#ff00ff;"> ,</span><span style="color:#0000ff;"> sizeof</span><span style="color:#ff00ff;">(</span></strong>sccno<strong><span style="color:#ff00ff;">));</span><span style="color:#0000ff;"> for</span><span style="color:#ff00ff;">(</span><span style="color:blue;">int</span></strong> i<strong><span style="color:#ff00ff;">=</span></strong><span style="color:#cc3300;">0</span><strong><span style="color:#ff00ff;">;</span></strong>i<strong><span style="color:#ff00ff;"><</span></strong>n<strong><span style="color:#ff00ff;">;</span></strong>i<strong><span style="color:#ff00ff;">++)</span><span style="color:#0000ff;"> if</span><span style="color:#ff00ff;">(!</span></strong>pre<strong><span style="color:#ff00ff;">[</span></strong>i<strong><span style="color:#ff00ff;">]) {</span></strong> dfs<strong><span style="color:#ff00ff;">(</span></strong>i<strong><span style="color:#ff00ff;">);</span><span style="color:#0000ff;"> if</span><span style="color:#ff00ff;">(!</span></strong>flag<strong><span style="color:#ff00ff;">)</span><span style="color:#0000ff;"> return</span></strong><span style="color:#cc3300;"> 0</span><strong><span style="color:#ff00ff;">;}</span><span style="color:#0000ff;"> return</span></strong><span style="color:#cc3300;"> 1</span><strong><span style="color:#ff00ff;">; }</span><span style="color:blue;"> int</span><span style="color:#0000ff;"> main</span><span style="color:#ff00ff;">() {</span><span style="color:blue;"> int</span></strong> T<strong><span style="color:#ff00ff;"> ,</span></strong> kcase<strong><span style="color:#ff00ff;"> =</span></strong><span style="color:#cc3300;"> 1</span><strong><span style="color:#ff00ff;">;</span><span style="color:blue;"> int</span></strong> N<strong><span style="color:#ff00ff;"> ,</span></strong> M<strong><span style="color:#ff00ff;"> ,</span></strong> K<strong><span style="color:#ff00ff;">;</span></strong> scanf<strong><span style="color:#ff00ff;">(</span></strong><span style="color:green;">"%d"</span><strong><span style="color:#ff00ff;">,&</span></strong>T<strong><span style="color:#ff00ff;">);</span><span style="color:#0000ff;"> while</span><span style="color:#ff00ff;">(</span></strong>T<strong><span style="color:#ff00ff;">--) {</span></strong> scanf<strong><span style="color:#ff00ff;">(</span></strong><span style="color:green;">"%d%d"</span><strong><span style="color:#ff00ff;">,&</span></strong>N<strong><span style="color:#ff00ff;">,&</span></strong>M<strong><span style="color:#ff00ff;">);</span></strong> K<strong><span style="color:#ff00ff;"> =</span></strong><span style="color:#cc3300;"> 9</span><strong><span style="color:#ff00ff;">;</span></strong>s<strong><span style="color:#ff00ff;"> =</span></strong><span style="color:#cc3300;"> 0</span><strong><span style="color:#ff00ff;"> ,</span></strong> t<strong><span style="color:#ff00ff;"> =</span></strong> N<strong><span style="color:#ff00ff;"> +</span></strong> M<strong><span style="color:#ff00ff;"> +</span></strong><span style="color:#cc3300;"> 1</span><strong><span style="color:#ff00ff;">;</span></strong> n<strong><span style="color:#ff00ff;"> =</span></strong> t<strong><span style="color:#ff00ff;"> +</span></strong><span style="color:#cc3300;"> 1</span><strong><span style="color:#ff00ff;">;</span></strong> init<strong><span style="color:#ff00ff;">();</span><span style="color:blue;"> int</span></strong> sumr<strong><span style="color:#ff00ff;"> =</span></strong><span style="color:#cc3300;"> 0</span><strong><span style="color:#ff00ff;"> ,</span></strong> sumc<strong><span style="color:#ff00ff;"> =</span></strong><span style="color:#cc3300;"> 0</span><strong><span style="color:#ff00ff;">;</span><span style="color:blue;"> int</span></strong> x<strong><span style="color:#ff00ff;">;</span><span style="color:#0000ff;"> for</span><span style="color:#ff00ff;">(</span><span style="color:blue;">int</span></strong> i<strong><span style="color:#ff00ff;">=</span></strong><span style="color:#cc3300;">1</span><strong><span style="color:#ff00ff;">;</span></strong>i<strong><span style="color:#ff00ff;"><=</span></strong>N<strong><span style="color:#ff00ff;">;</span></strong>i<strong><span style="color:#ff00ff;">++) {</span></strong> scanf<strong><span style="color:#ff00ff;">(</span></strong><span style="color:green;">"%d"</span><strong><span style="color:#ff00ff;">,&</span></strong>x<strong><span style="color:#ff00ff;">);</span></strong> AddEdge<strong><span style="color:#ff00ff;">(</span></strong>s<strong><span style="color:#ff00ff;"> ,</span></strong> i<strong><span style="color:#ff00ff;"> ,</span></strong> x<strong><span style="color:#ff00ff;">);</span></strong> sumr<strong><span style="color:#ff00ff;"> +=</span></strong> x<strong><span style="color:#ff00ff;">; }</span><span style="color:#0000ff;"> for</span><span style="color:#ff00ff;">(</span><span style="color:blue;">int</span></strong> i<strong><span style="color:#ff00ff;">=</span></strong><span style="color:#cc3300;">1</span><strong><span style="color:#ff00ff;">;</span></strong>i<strong><span style="color:#ff00ff;"><=</span></strong>M<strong><span style="color:#ff00ff;">;</span></strong>i<strong><span style="color:#ff00ff;">++) {</span></strong> scanf<strong><span style="color:#ff00ff;">(</span></strong><span style="color:green;">"%d"</span><strong><span style="color:#ff00ff;">,&</span></strong>x<strong><span style="color:#ff00ff;">);</span></strong> AddEdge<strong><span style="color:#ff00ff;">(</span></strong>i<strong><span style="color:#ff00ff;"> +</span></strong> N<strong><span style="color:#ff00ff;"> ,</span></strong> t<strong><span style="color:#ff00ff;"> ,</span></strong> x<strong><span style="color:#ff00ff;">);</span></strong> sumc<strong><span style="color:#ff00ff;"> +=</span></strong> x<strong><span style="color:#ff00ff;">; }</span></strong> printf<strong><span style="color:#ff00ff;">(</span></strong><span style="color:green;">"Case #%d: "</span><strong><span style="color:#ff00ff;">,</span></strong>kcase<strong><span style="color:#ff00ff;">++);</span><span style="color:#0000ff;"> if</span><span style="color:#ff00ff;"> (</span></strong>sumr<strong><span style="color:#ff00ff;"> !=</span></strong> sumc<strong><span style="color:#ff00ff;">){</span></strong> printf<strong><span style="color:#ff00ff;">(</span></strong><span style="color:green;">"So naive!\n"</span><strong><span style="color:#ff00ff;">);</span><span style="color:#0000ff;">continue</span><span style="color:#ff00ff;">; }</span><span style="color:#0000ff;"> for</span><span style="color:#ff00ff;">(</span><span style="color:blue;">int</span></strong> i<strong><span style="color:#ff00ff;">=</span></strong><span style="color:#cc3300;">1</span><strong><span style="color:#ff00ff;">;</span></strong>i<strong><span style="color:#ff00ff;"><=</span></strong>N<strong><span style="color:#ff00ff;">;</span></strong>i<strong><span style="color:#ff00ff;">++) {</span><span style="color:#0000ff;"> for</span><span style="color:#ff00ff;">(</span><span style="color:blue;">int</span></strong> j<strong><span style="color:#ff00ff;">=</span></strong><span style="color:#cc3300;">1</span><strong><span style="color:#ff00ff;">;</span></strong>j<strong><span style="color:#ff00ff;"><=</span></strong>M<strong><span style="color:#ff00ff;">;</span></strong>j<strong><span style="color:#ff00ff;">++) {</span></strong> AddEdge<strong><span style="color:#ff00ff;">(</span></strong>i<strong><span style="color:#ff00ff;"> ,</span></strong> j<strong><span style="color:#ff00ff;"> +</span></strong> N<strong><span style="color:#ff00ff;"> ,</span></strong> K<strong><span style="color:#ff00ff;">); } }</span><span style="color:blue;"> int</span></strong> ans<strong><span style="color:#ff00ff;"> =</span></strong> Maxflow<strong><span style="color:#ff00ff;">();</span><span style="color:#0000ff;"> if</span><span style="color:#ff00ff;">(</span></strong>ans<strong><span style="color:#ff00ff;"> !=</span></strong> sumr<strong><span style="color:#ff00ff;">) {</span></strong> printf<strong><span style="color:#ff00ff;">(</span></strong><span style="color:green;">"So naive!\n"</span><strong><span style="color:#ff00ff;">);</span><span style="color:#0000ff;"> continue</span><span style="color:#ff00ff;">; }</span><span style="color:#0000ff;"> if</span><span style="color:#ff00ff;">(</span></strong>find_scc<strong><span style="color:#ff00ff;">())</span></strong> printf<strong><span style="color:#ff00ff;">(</span></strong><span style="color:green;">"So simple!\n"</span><strong><span style="color:#ff00ff;">);</span><span style="color:#0000ff;"> else</span></strong> printf<strong><span style="color:#ff00ff;">(</span></strong><span style="color:green;">"So young!\n"</span><strong><span style="color:#ff00ff;">); }</span><span style="color:#0000ff;"> return</span></strong><span style="color:#cc3300;"> 0</span><strong><span style="color:#ff00ff;">; }</span></strong>
HDOJ 4888 Redraw Beautiful Drawings && HDOJ 4975 A simple Gaussian elimination problem
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。