Կտրատիր Գրաֆը
Հեղինեն նվեր է ստացել կշռված գրաֆ՝ կազմված
N գագաթներից և M կողերից։ Ալեքսն ու Ռոբերտը տեսնելով Հեղինեի նվերը, որոշել են ընտրել որևէ K բնական թիվ և գրաֆը դանակով բաժանել երկու մասի հետևյալ սկզբունքով՝vհամարով գագաթը կլինի առաջին մասում, եթե[(v-1)/K]-ըզույգ է։
vհամարով գագաթը կլինի երկրորդ մասում, եթե[(v-1)/K]-ըկենտ է։
(
[x]-ով նշանակում ենք x-ը չգերազանցող ամենամեծ ամբողջ թիվը) Գրաֆը 2 մասի բաժանելուց հետո Ալեքսն ու Ռոբերտը հաշվելու են այն կողերի կշիռների գումարը, որոնք միացնում են տարբեր մասերի պատկանող գագաթներ։ Նրանք ցանկանում են K թիվը ընտրել այնպես, որ ստացվող գումարը լինի հնարավորինս մեծ։Պետք է պարզել հնարավոր ամենամեծ գումարը, որ կարող են ստանալ։
Մուտքային տվյալներ
Առաջին տողերում տրված են
N և M թվերը (1 ≤ N ≤ 1000, 1 ≤ M ≤ 1000000)Հաջորդ M տողերից յուրաքանչյուրում տրված են լինելու կողը նկարագրող 3 թվեր՝ A[i], B[i], W[i] (1 ≤ A[i], B[i] ≤ N, -109 ≤ W[i] ≤ 109). միացվող գագաթների համարները և կողի կշիռը (A[i] և B[i] թվերը կարող են լինել հավասար, միևնույն A[i], B[i] զույգը կարող է հանդիպել 1-ից ավելի անգամ):Ելքային տվյալներ
Պետք է արտածել մեկ թիվ՝ հնարավոր ամենամեծ գումարը։
Ենթախնդիրներ
- Ենթախնդիր 0 (0 միավոր) Օրինակները,
- Ենթախնդիր 1 (6 միավոր)
N ≤ 16
- Ենթախնդիր 2 (11 միավոր)
N ≤ 100
- Ենթախնդիր 3 (24 միավոր)
M = N-1, A[i] = i և B[i] = i+1
- Ենթախնդիր 4 (59 միավոր) Առանց լրացուցիչ սահմանափակումների,
Օրինակ
Մուտք | Ելք |
3 3
1 2 2
3 2 4
1 3 3 | 7 |
4 5
1 2 -1
2 3 3
3 4 6
4 1 2
1 3 -6 | 10 |
Բացատրություն
Առաջին օրինակում
K=2 ընտրելու դեպքում գրաֆի բաժանումը կլինի [1,2] և [3], իսկ գումարը կլինի 3+4=7։Երկրորդ օրինակում
K=1 ընտրելու դեպքում գրաֆի բաժանումը կլինի [1,3] և [2,4], իսկ գումարը կլինի -1+3+6+2=10
Աղբյուրը՝ Հանրապետական 2022
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB