国产探花免费观看_亚洲丰满少妇自慰呻吟_97日韩有码在线_资源在线日韩欧美_一区二区精品毛片,辰东完美世界有声小说,欢乐颂第一季,yy玄幻小说排行榜完本

首頁(yè) > 學(xué)院 > 開(kāi)發(fā)設(shè)計(jì) > 正文

bzoj1562 [NOI2009]變換序列

2019-11-10 19:52:47
字體:
來(lái)源:轉(zhuǎn)載
供稿:網(wǎng)友

Description

Input

Output

Sample Input

51 1 2 2 1

Sample Output

1 2 4 0 3

HINT

30%的數(shù)據(jù)中N≤50;60%的數(shù)據(jù)中N≤500;100%的數(shù)據(jù)中N≤10000。

正解:匈牙利算法。

這題給他們考試。。沒(méi)人想到二分圖匹配。有兩人想到用網(wǎng)絡(luò)流做可行解,給了4分部分分,其他人都是爆搜。。實(shí)在覺(jué)得這題不是很難吧。。

看完題目以后就能發(fā)現(xiàn)這是一道裸的二分圖匹配。如果用網(wǎng)絡(luò)流做,dinic無(wú)法保證最優(yōu)解,EK會(huì)超時(shí)。那么可以考慮用匈牙利算法。只要保證遍歷與一個(gè)點(diǎn)相連的邊按照相連點(diǎn)從小到大的順序就行,因?yàn)閷?duì)于單一的一個(gè)點(diǎn)來(lái)說(shuō),如果增廣了一條路徑就不會(huì)再增廣了。而對(duì)于全局則從最后一個(gè)點(diǎn)開(kāi)始增廣,因?yàn)楹笤鰪V的路徑會(huì)覆蓋掉先增廣的路徑。

//It is made by wfj_2048~#include <algorithm>#include <iostream>#include <cstring>#include <cstdlib>#include <cstdio>#include <vector>#include <cmath>#include <queue>#include <stack>#include <map>#include <set>#define inf (1<<30)#define il inline#define RG register#define ll long long#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)using namespace std;int g[30010][5],match[30010],vis[30010],n;il int gi(){    RG int x=0,q=1; RG char ch=getchar(); while ((ch<'0' || ch>'9') && ch!='-') ch=getchar();    if (ch=='-') q=-1,ch=getchar(); while (ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar(); return q*x;}il int dfs(RG int x,RG int cnt){    for (RG int i=1;i<=2;++i){	RG int v=g[x][i]; if (vis[v]==cnt) continue; vis[v]=cnt;	if (match[v]==-1 || dfs(match[v],cnt)){	    match[v]=x,match[x]=v; return 1;	}    }    return 0;}il void work(){    n=gi(); RG int x,flag=1,cnt=0;    for (RG int i=0;i<n;++i){	x=gi(); g[i][1]=i+x; if (g[i][1]>=n) g[i][1]-=n;	g[i][2]=i-x; if (g[i][2]<0) g[i][2]+=n;	if (g[i][1]>g[i][2]) swap(g[i][1],g[i][2]);	g[i][1]+=n,g[i][2]+=n;    }    memset(match,-1,sizeof(match));    for (RG int i=n-1;i>=0;--i) if (!dfs(i,++cnt)){ flag=0; break; }    if (!flag){ PRintf("No Answer"); return; } printf("%d",match[0]-n);    for (RG int i=1;i<n;++i) printf(" %d",match[i]-n); return;}int main(){    File("transform");    work();    return 0;}


發(fā)表評(píng)論 共有條評(píng)論
用戶名: 密碼:
驗(yàn)證碼: 匿名發(fā)表
主站蜘蛛池模板: 通化县| 正阳县| 张北县| 平顶山市| 洛南县| 和硕县| 夏河县| 常德市| 格尔木市| 子长县| 含山县| 西充县| 珲春市| 红桥区| 滦平县| 康乐县| 大渡口区| 青龙| 姜堰市| 子长县| 容城县| 灯塔市| 且末县| 尚志市| 岚皋县| 南陵县| 壤塘县| 壶关县| 凌云县| 邵武市| 封开县| 成都市| 仁怀市| 钦州市| 沅陵县| 河津市| 会昌县| 元朗区| 九龙坡区| 北川| 磴口县|