#
這是我們隊第二場多校聯合的比賽，雖然比賽不是太順利，但還是出了三題，排名50+。賽前還是按照慣例分題，我看后面，小波波看前面，阿登中間，我先看到1009，發現是個背包問題（貌似又加深了點），就扔給了小波波，小波波說第一題是個圖的問題，于是我們交換了題目，我看第一題，小波波看第九題，這個時候阿登說1005是個計算幾何，就先開始敲了，看完第一題，我發現實在是沒有想法，于是就看了一下當時過得也比較多的1004，看完之后發現是個拆點的最小割，而且比較確定了，由于機器有人在用，我先看了別的題目，后來阿登的代碼敲好了，交上去wa,小波波開始敲他的DP,考慮了很多種特殊情況之后，1Y了，然后我開始敲最小割，拆點，半個小時之后也過掉了。這時阿登還在改代碼，我和小波波開始想別的可做的題，于是看到了1010，剛開始的時候對題意不是太了解，過了將近2個小時之后才發現clarification里面有人問星星的光線是不是平行光，admin的回答是YES,于是就豁然開朗了，一個簡單的公式，秒殺。之后的過程比較無奈，阿登的計算幾何題交了好多次都沒過，可能是精度的原因，第一題到最后一個小時有40個人過，可是我們卻沒有想法，賽后問了問，發現原來這道題在FOJ專場出現過類似的題目，囧。難怪被人秒。。。
這次比賽暴露了我們的一個小弱點，就是第一個小時搶題的能力較弱，我記得我們是在1個小時以后才出的第一題，這個以后要加強訓練。
摘要: 此題如果一下子想到了思路確實是應該很快出的，這題暴露了我基本功不扎實的弱點，對qsort中cmp函數和sort中cmp函數的使用沒有完全弄明白，通過這題終于搞明白了啊，初學者如果只是按網上的寫法套個模板還是遠遠不夠的，因為解決的問題是在不斷變化的，一定要深入研究其原理，才能遇神殺神，遇佛殺佛。 ...
閱讀全文
今天是我們第一次參加多校聯合集訓的比賽，比賽開始前，我們還是按照以前的慣例進行分題，我看后面，小波波看前面，阿登看中間，大概十分鐘以后，我們看了下board,發現1001和1008已經有人過了（快得令人汗顏啊…）,于是我們馬上開始看1008，題意大概是給你N個數，這N個數只能是0或者是1，題目讓你求出不包含101的數字串有多少個。起初我們想用數學方法去計算，但是發現去重很麻煩，一時卡住了，后來小波波突然想到一個dp的方法，AC了。然后大家開始看1001，小波波想到如果所有的結點被擴展的時候花費的步數是偶數，那么輸出YES,否則NO,但是用DFS窮搜所有路徑的想法復雜度太高被我否決掉了，既然DFS不行，BFS行不行呢，其實結點只需要最多擴展兩次就行了，如果對原圖進行一下BFS復雜度大概只需要O(n)，我和阿登合計了一下，覺得可行，然后阿登就開始敲了。我和小波波開始看其他題目，我看了1007，小波波看1005，1005要求good sequences,推公式，既然要都相同或者都不相同，那么對M做一個全排列是滿足要求的，還有就是所有數是一樣的也滿足要求，我想了一下，也沒發現什么反例，這個時候阿登的代碼敲好了，但是一開始wa,我們把代碼發到阿登機器上再檢查一下，小波波先寫代碼，提交，不過一開始wa了，是算法還是特殊數據的問題？這個時候阿登說他找到了源程序里面的Bug,提交，過了。對于1005，我們發現一組特例，就是當n等于1, 其實對它做全排列和所有數字都一樣其實是一種情況，另外還有一種M等于2的情況也是特例，改了一下，也過了。我一直在考慮1007其實就是一個比較典型的行列轉換的問題，我記得以前在FOJ上做過，劉汝佳的書上也有提到，當時是用雙向廣搜，但是n,m<10,而這道題n,m<=100，用搜索肯定不行，怎么辦呢，把原矩陣的第一列全部處理成0，然后用枚舉目標矩陣中的每一列，再列進行排序，如果排序后兩個矩陣完全相等，輸出YES.這題敲代碼也確實比較快，但是交上去卻wa了，于是我和小波波一起逐行檢查，終于發現原來是一個<=寫成<了，囧啊！改了之后就過了。。。無語。我在查代碼的時候，阿登看了1009，說是線段樹，于是我把代碼發到自己機器上，阿登開始寫線段樹，剛開始過這道題的人很少，就寥寥幾個，但是阿登非常確定是線段樹，那就敲吧。在我過了1007之后沒多少時間，1009也過了。這時比賽還有大概一個小時吧，我們想再開一題，于是就各自看了幾道AC率比較低的題目，阿登看了下最后一題說最后一題可以做，就是用鏈表模擬一下，但是對于取反操作，如果用單鏈表的話，一次取反操作復雜度是N，操作次數一多肯定超時，這題有點遺憾，我當時再看1003，等我看完最后一題，我覺得其實可以用雙向鏈表的，后來大家也覺得雙向鏈應該是正解，但是卻沒有時間了，只能賽后再研究下了.
定義：
歐拉回路：每條邊恰好只走一次，并能回到出發點的路徑
歐拉路徑：經過每一條邊一次，但是不要求回到起始點
①首先看歐拉回路存在性的判定：
一、無向圖
每個頂點的度數都是偶數，則存在歐拉回路。
二、有向圖（所有邊都是單向的）
每個節頂點的入度都等于出度，則存在歐拉回路。
三.混合圖歐拉回路
混合圖歐拉回路用的是網絡流。
把該圖的無向邊隨便定向，計算每個點的入度和出度。如果有某個點出入度之差為奇數，那么肯定不存在歐拉回路。因為歐拉回路要求每點入度 = 出度，也就是總度數為偶數，存在奇數度點必不能有歐拉回路。
好了，現在每個點入度和出度之差均為偶數。那么將這個偶數除以2，得x。也就是說，對于每一個點，只要將x條邊改變方向（入>出就是變入，出>入就是變出），就能保證出 = 入。如果每個點都是出 = 入，那么很明顯，該圖就存在歐拉回路。
現在的問題就變成了：我該改變哪些邊，可以讓每個點出 = 入？構造網絡流模型。首先，有向邊是不能改變方向的，要之無用，刪。一開始不是把無向邊定向了嗎？定的是什么向，就把網絡構建成什么樣，邊長容量上限1。另新建s和t。對于入 > 出的點u，連接邊(u, t)、容量為x，對于出 > 入的點v，連接邊(s, v)，容量為x（注意對不同的點x不同）。之后，察看是否有滿流的分配。有就是能有歐拉回路，沒有就是沒有。歐拉回路是哪個？查看流值分配，將所有流量非 0（上限是1，流值不是0就是1）的邊反向，就能得到每點入度 = 出度的歐拉圖。
由于是滿流，所以每個入 > 出的點，都有x條邊進來，將這些進來的邊反向，OK，入 = 出了。對于出 > 入的點亦然。那么，沒和s、t連接的點怎么辦？和s連接的條件是出 > 入，和t連接的條件是入 > 出，那么這個既沒和s也沒和t連接的點，自然早在開始就已經滿足入 = 出了。那么在網絡流過程中，這些點屬于“中間點”。我們知道中間點流量不允許有累積的，這樣，進去多少就出來多少，反向之后，自然仍保持平衡。
所以，就這樣，混合圖歐拉回路問題，解了。
②.歐拉路徑存在性的判定
一。無向圖
一個無向圖存在歐拉路徑，當且僅當 該圖所有頂點的度數為偶數 或者 除了兩個度數為奇數外其余的全是偶數。
二。有向圖
一個有向圖存在歐拉路徑，當且僅當 該圖所有頂點的度數為零 或者 一個頂點的度數為1，另一個度數為-1，其他頂點的度數為0。
三。混合圖歐拉路徑
其實整篇文章只有這部分是我寫的哈，灰常不好意思，只是網上的同志們寫的太好了，實在沒有必要重復勞動，不知道大家有沒有發現，求歐拉路徑的第一步一定是求歐拉回路，在混合圖上也不例外，如何判斷混合圖歐拉回路問題的存在性呢？首先，我們用上文所說的方法判斷該圖是否存在歐拉回路，如果存在，歐拉路徑一定存在。如果歐拉回路不存在，那么我們枚舉歐拉路徑的起點和終點，連接一條無向邊，然后再用最大流判斷是否存在歐拉回路即可。
OJ上的幾道題 ：POJ 1386 HDOJ 3472
網絡流
題目描述：已知之前的一些比賽雙方和結果，和未來的賽事安排，問DD能否奪冠，不能并列
我們談心的讓未來DD參加的比賽都贏，且我們可以知道未來每個人最多可以贏幾場
給所有選手編號，預先統計出所有選手已經勝利的場次，然后對所有還沒有進行的比賽，假設其中任意一個選手獲勝，并統計勝負關系，（加入每個人勝利的次數在w[]中，每兩個選手互相對戰勝利的次數在a[][]中）即某兩個選手a,b進行比賽a贏b的次數和b贏a的次數，這里要注意的是兩個選手進行比賽，你假設任意一個選手獲勝都是正確的，待會你會發現其實假設僅僅只是假設。增加超級源超級匯，超級源向每一個結點射出一條容量是這個點勝利場次的邊，所有的點向匯點連一條容量是w[ID[DD]]-1的邊，顯然是為了限制每個點的勝利次數不能大于等于DD.中間任意兩個結點根據勝負關系建立一條容量是a[i][j]的邊，跑一遍最大流即可，如果滿流，說明有可行解，否則無解。
下面來分析一下構圖的原理，超級源向所有選手連一條容量是他將要獲勝場次的邊，比如說是c，說明這個選手有c場勝利要分配，如果這條邊上的流量直接流向了匯點，說明該選手獲勝，如果流量通過有向邊流向了他的對手，說明這個勝利果實被他的對手拿走了，也就是實際上輸掉了比賽，所以我才說假設僅僅是假設。再加上有每個點到匯點的限流，跑一遍最大流如果能滿流說明比賽可以合理的分配勝負關系使得每個人的勝利場次都不超過DD,如果不能，無解。
這題構圖確實很精彩，贊！
摘要:
弄了一天，總算搞懂了掃描線是怎么回事，剛開始的時候在網上搜索，代碼基本沒有注釋，很難看懂，隨后搜索到了陳宏的論文，2頁紙能寫完的東西，他居然可以寫那么長，粗略的掃描了一下，感覺原線段和超元線段的定義很不錯，其他的實在講的有點羅嗦就跳過了。鑒于以后還會有同樣想要學習掃描線的同學，下面我來簡單的介紹一...
閱讀全文
摘要: 250 Points枚舉每一個要求的數字，求它到左上角的最小步數即可。注意數字可以穿越邊界。
#define INF 1000000000int n,m;int cnt(int x,int y){ int res=INF; if(abs...
閱讀全文
原來網絡流也能二分，今天終于見識了。。。
二分+最大流
題目大意：給定n個人m場比賽，問贏的最多的人最少贏幾場
二分答案，增加源匯點，左邊一排是比賽點，右邊是球員，若有比賽，比賽向倆球員連容量為1的邊
源點向比賽連容量為1的邊，球員向匯點連容量為二分枚舉值的邊，判斷是最大流是否等于比賽個數
網絡流的構圖真是個神奇的東西，我承認如果不看網上的解題報告，我真的很難想到，首先是題意不太明確，剛開始我還以為贏的最多的選手勝利的場次必須是最多的。。。但是從樣例來看，貌似就算每個人都贏一場也會有冠軍出現。。。說說我的理解吧，從超級源點引一條邊至代表每場比賽的節點，限制每場比賽的勝利者只有一個人，這個流量如果在射出到某個選手的一條邊中，代表這場比賽是他取勝。每個選手到匯點連一條二分枚舉的邊，就是限制勝利場次的上界，如果最后的最大流等于m,說明這m場比賽的的勝者可以合理的分配，如果不能，說明比賽不能正常進行。又可以分析得出，如果某一個二分值mid滿足要求，那么比他大的值一定也滿足要求。故可二分枚舉答案。（PS:這題的復雜度應該是(10000+10000+2)^2*(m*2+m+n)*log 10000.總覺得要超時啊。。。難道數據弱了？）
int n,m;
struct node2
{
int a,b;
}re[100000];
bool check(int n,int m,int mid)
{
int i;
for(i=0;i<n+m+2;i++)
adj[i]=NULL;
len=0;
int s=n+m;
int t=s+1;
for(i=0;i<m;i++)
insert(s,i,1);
for(i=0;i<n;i++)
insert(m+i,t,mid);
for(i=0;i<m;i++)
{
insert(i,m+re[i].a,1);
insert(i,m+re[i].b,1);
}
return dinic(t+1,s,t)==m;
}
int main()
{
int i;
while(scanf("%d%d",&n,&m)!=EOF)
{
for(i=0;i<m;i++)
{
scanf("%d%d",&re[i].a,&re[i].b);
re[i].a--;
re[i].b--;
}
int l=1,r=m;
int ans=-1;
while(l<=r)
{
int mid=(l+r)>>1;
if(check(n,m,mid))
{
ans=mid;
r=mid-1;
}
else
l=mid+1;
}
printf("%d\n",ans);
}
return 0;
}
題意就是N個學校，每個學校有一個編號，編號可以重復。現在要求每個學校有一個獨立的編號，但是每個學校可以接受的編號有一個范圍，在這個范圍內，編號每變動1將付出的話費是D。求是否有可行方案并給出最小花費。
顯然X部分是所有的學校，Y部分是新的編號，按順序我們把學校設置成1—N,設置超級源點s,s向每個X側的節點連一條費用是0，流量是1的邊，把他們對應的編號設置成節點N+1- 2*N,X部和Y部的邊用計算出來的花費連邊，流量是1，Y部每個節點向t連一條費用是0流量是1的邊，求最小費用最大流即可。
模板就不貼了，構圖部分代碼如下：
void creat(int n,int s,int t)
{
flowsum=0;
int a,b,c,d;
int i;
for(i=1;i<=n;i++)
{
insert(s,i,1,0);
insert(i+n,t,1,0);
scanf("%d%d%d%d",&a,&b,&c,&d);
int j;
for(j=b;j<=c;j++)
{
insert(i,j+n,1,abs(j-a)*d);
}
}
}
void init(int n)
{
int i;
for(i=0;i<n;i++)
adj[i]=NULL;
len=0;
}
int main()
{
int n;
int s,t;
scanf("%d",&n);
init(2*n+2);
s=0;
t=2*n+1;
creat(n,s,t);
int ans=mincostflow(t+1,s,t);
if(flowsum!=n)
printf("NIE\n");
else
printf("%d\n",ans);
return 0;
}
題目大意：n個小朋友投票，定義投票的沖突數為好友間發生沖突數加上所有和自己意愿發生沖突的人數，求沖突最少數
分析：增加源匯點，s向所有同意的連容1的邊，所有反對的向t連容1的邊，若倆人是好友，則相互連容1邊
對于經過好友間的流量，表示著沖突，即可用沖突或改變意愿來替代，那么最小割就成了沖突數的定義
看到網上的幾個代碼都進行了拆點，我覺得似乎沒有必要，直接構圖，AC.看來感覺是對的，但我有些疑惑的是為什么要把正反兩條邊都建起來，后來想了一下，其實最小割模型中有個偏序的關系，模型的一側是包含s的一組結點，右側是包含t的一組結點，而SET(S)到SET(T)應該是相連的，而如果建成單相邊的話，有可能導致S,T之間沒有路徑存在。而最小割中恰好又只取S->T的邊，所以無論關系是怎樣的，都可以滿足要求，取兩個朋友之間的一條邊，此題得解。