ACM_Someone like you

摘要： 1 /* 2 題意：軍隊坐bus去機場 n個節點（bus）m條公交通路（單向） 3 每走一條路花時間1 問最少破壞幾個結點（是相關聯的的路都不能走) 4 使軍隊在至少k時間不能到達機場。 5 思路：求最小割（等于最大流） 6 建(新)圖：弗洛伊德求出任意兩點最短路（dist[a][b]） 7 核心判斷dist(1,a)+dist(b,n)之和滿足小于k 則建邊addedge(n+a,b,INF) 8 9 addedge(i,i+n,1);//注意方向 10 11 start=n+1，end=n;totals=n+n; 12 sap();即可。 13 */ 14 #inc... 閱讀全文

摘要： 1 做得還算麻利~ 2 /*最大閉合子圖 3 題意：建通訊站。每個通訊站有一定耗費，兩個特定的通訊站之間建立通訊以后 4 會有一定收益，問怎樣建立通訊站可以使得收益最大 。 5 ——最大權閉合子圖->最小割 6 ——url：http://acm.hdu.edu.cn/showproblem.php?pid=3879 7 思路： 8 首先考慮將圖轉化。 9 即一條通訊線路有一定收益wi（即為正點權），但需要建立兩個通訊站， 10 這兩個通訊站有一定造價pi(即為負點權)。 11 將通訊線路也變成點，點權為收益，連兩條有向只向兩個通訊站。 12 原來的通訊站點權不變。則star... 閱讀全文

摘要： 1 /* 2 hdu 3917 Road constructions 最大權閉合圖 3 題意：n個城市 m個工程公司修路 每個公司要交稅收 有k個路段 分別花銷cost 4 當如果選擇了某個公司，該公司負責的所有的路都要選，還有如果1->2的路由公司A負責， 5 2->3的路由公司B負責，那么如果選了公司A就必須選公司B， 求最大的收益 6 建圖：稅收為正權值、cost為負權值 start連所有公司m end連所有公司m 7 規則要求聯系的公司之間為INF eg addedge(a,b,INF);該處解決方法建結構體詳見具體代碼 8 ... 閱讀全文

摘要： View Code 1 #include <iostream> 2 #include<cstdio>//最大流SAP 3 #include<cstring> 4 #include<vector> 5 #include<queue> 6 #include<algorithm> 7 using namespace std; 8 #define min(a,b) ((a)<(b))?(a):(b) 9 #define max(a,b) ((a)>(b))?(a):(b) 10 #define MAXN 200 11 閱讀全文

摘要： View Code 1 #include <iostream>//SAP 最大流應用 2 #include<cstdio> 3 #include<cstring> 4 #include<vector> 5 #include<queue> 6 #include<algorithm> 7 using namespace std; 8 #define min(a,b) ((a)<(b))?(a):(b) 9 #define max(a,b) ((a)>(b))?(a):(b) 10 #define MAXN 1111 閱讀全文

摘要： View Code 1 /* 2 http://acm.hdu.edu.cn/webcontest/contest_showproblem.php?pid=1001&ojid=0&cid=4456&hide=0 3 4 hdu Drainage Ditches 5 */ 6 #include <iostream> 7 #include<cstdio> 8 #include<cstring> 9 #include<vector> 10 #include<queue> 11 #include<algorith 閱讀全文

摘要： 刷刷水 牛人們說 可是我連水都覺得難 只得向牛人們學習 希望日積月累后 我的圖論水平也可以自豪地說“ 刷刷水”View Code 1 /* 2 題意：jimmy下班需要穿過一個森林。勞累一天后在森林中漫步是見非常愜意的事， 3 所以他打算每天沿著不同的路徑回家，欣賞不同的風景。但他也不想太晚回家， 4 因此他不打算走回頭路。換句話說，他只沿（A，B）走， 5 存在一條從B出發回家的路徑比所有從A出發回家的路徑都短。 6 你的任務是計算一共有多少條不同的回家路徑 7 分析： 首先求每個點到家的最短路d[u];//dijkstra 8 深搜 每個點出發有幾條可行路徑... 閱讀全文

摘要： Root :: AOAPC I: Beginning Algorithm Contests -- Training Guide (Rujia Liu) :: Chapter 1. Algorithm Design :: Designing Efficient Algorithms :: Examples/*題意：n個整數a1~an-1 找到兩個數ai aj 使ai-aj盡可能大(i<j) 直接的想法 找到每組（ai,aj）數對 max比較找到dmax 時間是n^2 超時(M=100000+10)思路：單位時間維護最大值，該題不用輸入都結束再處理數據（時間從n降到l） 可以邊輸入邊比較維護 閱讀全文

摘要： /*題意：一個整數n,計算操作次數，把序列（1~n）每次減去一個(1~n)的正整數最終使整個序列都歸為0 計算這個最小的操作次數方法：多在本子上畫畫，遞歸公式：f(n)=f(n/2)+1;*///AC 1 #include<stdio.h> 2 #include<string.h> 3 //1 ≤ N ≤ 1,000,000,000 int 足夠 4 int f(int n) 5 { 6 int c; 7 if(n==1)c=1; 8 else 9 {10 11 c=f(n/2)+1;12 }13 return c;14 }15... 閱讀全文

摘要： /*題目： 分金幣 圍著桌子坐n人 每人有一些金幣，大家之間可以相互給錢，最終使每個人擁有相同的金幣。求最小移動金幣個數。考查數學知識：中位數的距離的問題，見“解題手冊”P6頁其他沒有難度，注意找規律。邊學邊記吧 誰讓我笨了！題型可以舉一反三。注意。*///AC 1 #include<stdio.h> 2 #include<string.h> 3 //#include<cstdio> 4 #include<algorithm> 5 using namespace std; 6 const int M=1000010; 7 long long c[ 閱讀全文