北郵新入生ランキング6解題報告
48385 ワード
A.道路工事2014新入生夏休み個人ランキング06
時間制限3000 ms
メモリ制限65536 KB
タイトルの説明
弱い学校は道路を修理するのが好きで、今あなたに彼の学校の地図をあげて、地図の上でn点とm本の双方向の辺があって、それぞれの辺は1本の道を代表して、この道は通じるかもしれなくて、道路を修理しているかもしれません.道路工事で交通が不便であることはよく知られている.すべての弱さは学校が早く道を修理したいと思っています.彼は簡単に本館915に着いて問題を磨くことができます.しかし、学校の施工能力が限られていることを考慮して、弱さんはあなたに学校が集中してすぐに修理する必要がある最小の道路数を算出させたいと思っています.彼は学校の任意の点から出発して、工事中の道を通らずに本館に着くことができます(番号は1).
入力フォーマット
複数のデータがあります.各グループのデータはn(1<=n<=10000)、m(1<=m<=20000)で始まる.次の行にはm行数があります.行ごとに3つの数があり、u,v,sに対応し、それぞれこの道の両端点(番号1からn)と道路状況であり、s=0はスムーズを表し、s=1は道路工事中を表す.入力保証図は連通図です.
出力フォーマット
データのセットごとに対応する最小パス数を出力します.
入力サンプル
出力サンプル
時間制限3000 ms
メモリ制限65536 KB
タイトルの説明
弱い学校は道路を修理するのが好きで、今あなたに彼の学校の地図をあげて、地図の上でn点とm本の双方向の辺があって、それぞれの辺は1本の道を代表して、この道は通じるかもしれなくて、道路を修理しているかもしれません.道路工事で交通が不便であることはよく知られている.すべての弱さは学校が早く道を修理したいと思っています.彼は簡単に本館915に着いて問題を磨くことができます.しかし、学校の施工能力が限られていることを考慮して、弱さんはあなたに学校が集中してすぐに修理する必要がある最小の道路数を算出させたいと思っています.彼は学校の任意の点から出発して、工事中の道を通らずに本館に着くことができます(番号は1).
入力フォーマット
複数のデータがあります.各グループのデータはn(1<=n<=10000)、m(1<=m<=20000)で始まる.次の行にはm行数があります.行ごとに3つの数があり、u,v,sに対応し、それぞれこの道の両端点(番号1からn)と道路状況であり、s=0はスムーズを表し、s=1は道路工事中を表す.入力保証図は連通図です.
出力フォーマット
データのセットごとに対応する最小パス数を出力します.
入力サンプル
3 2
1 2 0
1 3 1
3 2
1 2 0
1 3 0
3 2
1 2 1
1 3 1出力サンプル
1
0
2 ...
#include <cstdio>
using
namespace
std;
const
int
MAXN=10001;
const
int
MAXM=400004;
int
par[MAXN];
struct
edge{
int
from,to;
};
edge e[MAXM];
int
n,m;
int
me;
int
fpar(
int
i){
if
(par[i]==i)
return
i;
else
return
par[i]=fpar(par[i]);}
bool
same(
int
a,
int
b){
return
(fpar(a)==fpar(b));}
void
unit(
int
a,
int
b){
if
(!same(a,b))par[fpar(a)]=fpar(b);}
int
kruskal(){
int
ret=0;
for
(
int
i=0;i<me;i++){
if
(!same(e[i].from,e[i].to)){
unit(e[i].from,e[i].to);
ret++;
}
}
return
ret;
}
int
solve(){
int
tf,tt,tc;
for
(
int
i=1;i<=n;i++){par[i]=i;}
me=0;
for
(
int
i=0;i<m;i++){
scanf
(
"%d%d%d"
,&tf,&tt,&tc);
if
(tc==0)unit(tf,tt);
else
{
if
(!same(tf,tt)){
e[me].from=tf;e[me].to=tt;me++;
e[me].from=tt;e[me].to=tf;me++;
}
}
}
int
ans=kruskal();
printf
(
"%d
"
,ans);
return
0;
}
int
main(){
while
(
scanf
(
"%d%d"
,&n,&m)==2){
solve();
}
return
0;
}
B:
B. 2014 06
4000 ms
65536 KB
n ， ， j i ， Hij.
。 n(n <= 18) 。 n ， n 。 i j Hij( Hij <= 10000) j i 。 Hii = 0, ， 。
。
2
0 1
2 0
3
0 -1 7
3 0 3
3 3 0
サンプル2
10
....... .... にn^n^2^nに っかかっているなんて#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXM=1<<18;
const int MINDP=-200000;
int dp[MAXM][18];
bool vis[MAXM][18];
int h[18][18];
int n;
int dfs(int last,int m){
//printf("dfs(%d,%d)begin
",last,m);
if(vis[m|(1<<last)][last]){
//printf("dp[%d][%d]%d
",(m|(1<<last)),last,dp[m|(1<<last)][last]);
return dp[m|(1<<last)][last];
}
if(m==0){
vis[1<<last][last]=true;
dp[1<<last][last]=0;
return 0;
}
dp[m|(1<<last)][last]=MINDP;
for(int i=0;i<n;i++){
if(m&(1<<i))dp[m|(1<<last)][last]=max( dp[m|(1<<last)][last],(dfs(i,(m^(1<<i)))+h[i][last]));
}
vis[m|(1<<last)][last]=true;
//printf("dp[%d][%d]%d
",(m|(1<<last)),last,dp[m|(1<<last)][last]);
return dp[m|(1<<last)][last];
}
int main(){
while(scanf("%d",&n)==1){
for(int i=1;i<=((1<<n)-1);i++)memset(vis[i],0,sizeof(vis[i]));
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
scanf("%d",&h[i][j]);
}
}
int maxn=(1<<n)-1;
//printf("maxn%d
",maxn);
for(int i=0;i<n;i++)dfs(i,(maxn^(1<<i)));
int maxans=MINDP;
for(int i=0;i<n;i++)maxans=max(maxans,dp[(1<<n)-1][i]);
printf("%d
",maxans);
}
return 0;
}
C: .... " "
449.
1000 ms
65536 KB
n ， 。
。
n， n ， 0 10000。
8.2MB。
， n 。
3
4 2 1
サンプル1 2 4
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXM=10001;
int n;
int num[MAXM];
int heap[MAXM];
int main(){
while(scanf("%d",&n)==1){
if(n==0)continue;
int pheap=0;
for(int i=0;i<n;i++){
int temp;
scanf("%d",&temp);
if(num[temp]==0){
heap[pheap++]=temp;
}
num[temp]++;
}
if(pheap<=1000){
sort(heap,heap+pheap);
for(int i=0;i<pheap;i++){
while(num[heap[i]]){
printf("%d",heap[i]);
n--;num[heap[i]]--;
if(n)printf(" ");
else printf("
");
}
}
continue;
}
for(int i=0;i<10001;i++){
while(num[i]){
printf("%d",i);
n--;num[i]--;
if(n)printf(" ");
else printf("
");
}
}
}
return 0;
}
D. 2014 06
1000 ms
65536 KB
， ， 。 。 Mays ， Luke ， ， ， ， ， ， Luke ， ～ ，Luke ， 。 Luke ， Luke 。
， 10 。 n，m， Luke ， ， m ， u，v， u,v ，1<=u,v<=n，1<=n,m<=100000
， ， 。
5 4
1 2
1 3
1 4
4 5
サンプル1
1 エッジを すると われたデータの しいポーズが きされます.vis を すると、「 または の1つのパス」しかないので、 にvis[true]のノード( ノード)を すればいいのですが、 サブツリーサイズを するとvisがすべて されるのでpre 2 を してコンパイラが されていないので しません...#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m;
const int MAXM= 100001;
int dp[MAXM];
int first[MAXM];
int to[2*MAXM];
int pre[MAXM];
int next[2*MAXM];
bool vis[MAXM];
int maxpoint,maxans;
int dfs(int s){
if(vis[s])return dp[s];
vis[s]=true;
dp[s]=0;
for(int p=first[s];p!=-1;p=next[p]){
if(vis[to[p]])continue;
int tempd=dfs(to[p]);
pre[to[p]]=s;
dp[s]+=tempd;
}
return ++dp[s];
}
void addedge(int tfrom,int tto,int index){
to[index]=tto;
next[index]=first[tfrom];
first[tfrom]=index;
}
int main(){
for(int ti=1;scanf("%d%d",&n,&m)==2;ti++){
memset(first,-1,sizeof(first));
memset(vis,0,sizeof(vis));
for(int i=0;i<m;i++){
int tfrom,tto;
scanf("%d%d",&tfrom,&tto);
addedge(tfrom,tto,2*i);addedge(tto,tfrom,2*i+1);
}
maxans=0;
maxpoint=0x7fffffff;
dfs(1);
for(int i=1;i<=n;i++){
int maxson=n-dp[i];
for(int p=first[i];p!=-1;p=next[p]){
if(pre[i]!=to[p])maxson=max(maxson,dp[to[p]]);
}
if(maxson<maxpoint){
maxpoint=maxson;maxans=i;
}
}
printf("%d
",maxans);
}
return 0;
}