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